On the complexity of embedding of graphs into grids with minimum congestion

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, the authors show that it is also NP-complete to detrmine whether G is embeddable in a k×n grid with unit congestion for any fixed integer k≥3. In addition, they 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, the authors suggest a linear time algorithm for recognizing graphs embeddable in a 2ו grid with unit congestion.