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

Akira MATSUBAYASHI  Shuichi UENO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E79-A   No.4   pp.469-476
Publication Date: 1996/04/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
NP-completeness,  graph embedding,  congestion,  grid,  VLSI layout,  

Full Text: PDF(652.5KB)>>
Buy this Article




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.