Small Congestion Embedding of Separable Graphs into Grids of the Same Size
Akira Matsubayashi · 2005
In this paper we consider the problem of embedding a (guest) graph into a grid with the same number of nodes as those of the guest graph with minimum edge congestion. We show that a graph which has some efficient recursive separators can be embedded into a grid of the same size with small congestion. Our results imply that an N-node planar graph with maximum vertex degree /spl Delta/ can be embedded into an N-node grid with congestion O (/spl Delta//sup 2/ log N), and if the graph is a tree, then it can be embedded into an N-node grid with congestion O(/spl Delta/). The congestion for trees is optimal within a constant factor, and the congestion for planar graphs is optimal within an O(min{/spl Delta//sup 2/ /spl radic/log N, /spl Delta/ log N}) factor.