The complexity of embedding of acyclic graphs into grids with minimum congestion
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 m x n-grid is NP-complete. In this paper, we show that the problem is still NP-complete if G is restricted to an acyclic graph.
grid graph embedding graph layout vlsi layout