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 wellknown 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 Δ can be embedded into an N-node d-dimensional grid with an edge-congestion of O(Δ2 logN) if d = 2, O(Δ2 log logN) if d = 3, and O(Δ2) otherwise. An N-node graph with maximum node degree Δ 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(Δ) for d ≥ 2