@inproceedings{oai:kanazawa-u.repo.nii.ac.jp:00009997,
 author = {Matsubayashi, Akira},
 book = {Proceedings - IEEE International Symposium on Circuits and Systems},
 month = {Jan},
 note = {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., 金沢大学理工研究域電子情報学系},
 pages = {2938--2941},
 publisher = {IEEE = Institute of Electrical and Electronics Engineers},
 title = {Separator-Based Graph Embedding into Higher-Dimensional Grids with Small Congestion},
 volume = {2009},
 year = {2009}
}