Separator-based graph embedding into higher-dimensional grids with small congestion

We study the problem of embedding a guest graph into an optimally-sized grid with minimum edge-congestion. Based on a well-known notion of graph separator, we prove that any guest graph can be embedded with a smaller edge-congestion as the guest graph has a smaller separator, and as the host grid has a higher dimension. Our results imply the following: An N-node planar graph with maximum node degree Delta can be embedded into an N-node d-dimensional grid with an edge-congestion of O(Delta² log N) if d = 2, O(Delta² log log N) if d = 3, and O(Delta²) otherwise. An N-node graph with maximum node degree Delta and a treewidth O(1), such as a tree, an outerplanar graph, and a series-parallel graph, can be embedded into an N-node d-dimensional grid with an edge-congestion of O(Delta) for d ges 2.