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