Small congestion embedding of separable graphs into grids of the same size

In this paper we consider the problem of embedding a (guest) graph into a grid with the same number of nodes as those of the guest graph with minimum edge congestion. We show that a graph which has some efficient recursive separators can be embedded into a grid of the same size with small congestion. Our results imply that an N-node planar graph with maximum vertex degree Δ can be embedded into an N-node grid with congestion O (Δ² log N), and if the graph is a tree, then it can be embedded into an N-node grid with congestion O(Δ). The congestion for trees is optimal within a constant factor, and the congestion for planar graphs is optimal within an O(min{Δ² √log N, Δ log N}) factor.