On the Complexity of Minimum Congestion Embedding of Acyclic Graphs into Ladders
Akira Matsubayashi · Institutional Repositories DataBase (IRDB) · 2001
It is known that the problem of determining, given a planar graph G and an integer m, whether there exists a congestion-1 embedding of G into an m × k-grid is NP-complete for a fixed integer k ≥ 3. It is also known that the problem for k = 3 is NP-complete even if G is restricted to an acyclic graph.The complexity of the problem for k = 2 was left open.In this paper, we show that for k = 2, the problem can be solved in polynomial time if G is restricted to a tree, while the problem is NP-complete even if G is restricted to an acyclic graph.