For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
The Complexity of Embedding of Acyclic Graphs into Grids with Minimum Congestion
Akira MATSUBAYASHI Masaya YOKOTA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2000/11/25
Print ISSN: 0916-8508
Type of Manuscript: LETTER
Category: Graphs and Networks
graph embedding, graph layout, VLSI layout, grid,
Full Text: PDF>>
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.