The Complexity of Embedding of Acyclic Graphs into Grids with Minimum Congestion

Akira MATSUBAYASHI  Masaya YOKOTA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E83-A   No.11   pp.2390-2394
Publication Date: 2000/11/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: LETTER
Category: Graphs and Networks
Keyword: 
graph embedding,  graph layout,  VLSI layout,  grid,  

Full Text: PDF>>
Buy this Article




Summary: 
It is known that the problem of determining, given a planar graph G and integers m and n, whether there exists a congestion-1 embedding of G into a two dimensional mn-grid is NP-complete. In this paper, we show that the problem is still NP-complete if G is restricted to an acyclic graph.