Separator-Based Graph Embedding into Higher-Dimensional Grids with Small Congestion

摘要

本報告では，グラフCを同じ点数のd次元格子グラフに小さい辺負荷で埋め込む問題を考え，Cの分割子が小さく，またdが大きいほど，より小さい辺負荷で埋め込み可能であることを示す．特に，最大次数△のN点平面グラフはd＝2のときO（△~2 log N），d＝3のときO（△~2 log log N），d≧4のときO（△~2）の辺負荷で埋め込めること，さらに，木，外平面グラフ，直並列グラフなど，O（1）の木幅を持つグラフは任意のd≧2に対してO（△）の辺負荷で埋め込めることを示す．%We study the problem of embedding a guest graph with minimum edge-congestion into a high dimensional grid of the same size as the guest graph. Based on a well-known notion of graph separator, we show 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 iV-node planar graph with maximum node degree A can be embedded into an TV-node d-dimensional grid with an edge-congestion of 0(△~2 log N) if d = 2, O(△~2 log log N) if d = 3, and O(△~2) otherwise. An iV-node graph with maximum node degree A and a treewidth O(1), such as a tree, an outerplanar graph, and a series-parallel graph, can be embedded into an iV-node d-dimensional grid with an edge-congestion of O(△) for d ≧ 2.