On the Complexity of Embedding of Graphs into Grids with Minimum Congestion

Akira MATSUBAYASHI; Shuichi UENO

On the Complexity of Embedding of Graphs into Grids with Minimum Congestion

Akira MATSUBAYASHI, Shuichi UENO

Full Text Views

0

Cite this

Summary :

It is known that the problem of determining, given a planar graph G with maximum vertex degree at most 4 and integers m and n, whether G is embeddable in an m n grid with unit congestion is NP-hard. In this paper, we show that it is also NP-complete to determine whether G is embeddable in ak n grid with unit congestion for any fixed integer k 3. In addition, we show a necessary and sufficient condition for G to be embeddable in a 2 grid with unit congestion, and show that G satisfying the condition is embeddable in a 2 |V(G)| grid. Based on the characterization, we suggest a linear time algorithm for recognizing graphs embeddable in a 2 grid with unit congestion.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E79-A No.4 pp.469-476

Publication Date: 1996/04/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Akira MATSUBAYASHI, Shuichi UENO, "On the Complexity of Embedding of Graphs into Grids with Minimum Congestion" in IEICE TRANSACTIONS on Fundamentals, vol. E79-A, no. 4, pp. 469-476, April 1996, doi: .
Abstract: It is known that the problem of determining, given a planar graph G with maximum vertex degree at most 4 and integers m and n, whether G is embeddable in an m n grid with unit congestion is NP-hard. In this paper, we show that it is also NP-complete to determine whether G is embeddable in ak n grid with unit congestion for any fixed integer k 3. In addition, we show a necessary and sufficient condition for G to be embeddable in a 2 grid with unit congestion, and show that G satisfying the condition is embeddable in a 2 |V(G)| grid. Based on the characterization, we suggest a linear time algorithm for recognizing graphs embeddable in a 2 grid with unit congestion.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e79-a_4_469/_p

Copy

@ARTICLE{e79-a_4_469,
author={Akira MATSUBAYASHI, Shuichi UENO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On the Complexity of Embedding of Graphs into Grids with Minimum Congestion},
year={1996},
volume={E79-A},
number={4},
pages={469-476},
abstract={It is known that the problem of determining, given a planar graph G with maximum vertex degree at most 4 and integers m and n, whether G is embeddable in an m n grid with unit congestion is NP-hard. In this paper, we show that it is also NP-complete to determine whether G is embeddable in ak n grid with unit congestion for any fixed integer k 3. In addition, we show a necessary and sufficient condition for G to be embeddable in a 2 grid with unit congestion, and show that G satisfying the condition is embeddable in a 2 |V(G)| grid. Based on the characterization, we suggest a linear time algorithm for recognizing graphs embeddable in a 2 grid with unit congestion.},
keywords={},
doi={},
ISSN={},
month={April},}

Copy

TY - JOUR
TI - On the Complexity of Embedding of Graphs into Grids with Minimum Congestion
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 469
EP - 476
AU - Akira MATSUBAYASHI
AU - Shuichi UENO
PY - 1996
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E79-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 1996
AB - It is known that the problem of determining, given a planar graph G with maximum vertex degree at most 4 and integers m and n, whether G is embeddable in an m n grid with unit congestion is NP-hard. In this paper, we show that it is also NP-complete to determine whether G is embeddable in ak n grid with unit congestion for any fixed integer k 3. In addition, we show a necessary and sufficient condition for G to be embeddable in a 2 grid with unit congestion, and show that G satisfying the condition is embeddable in a 2 |V(G)| grid. Based on the characterization, we suggest a linear time algorithm for recognizing graphs embeddable in a 2 grid with unit congestion.
ER -