## Minimum-Width Grid Drawings of Plane Graphs (Extended Abstract)
Chrobak, Marek and Nakano, Shin-Ichi
(1995)
Full text not available from this repository. ## AbstractGiven a plane graph G, we wish to draw it in the plane, according to the given embedding, in such a way that the vertices of G are drawn as grid points, and the edges are drawn as straight-line segments between their endpoints. An additional objective is to minimize the size of the resulting grid.It is known that each plane graph can be drawn in such a way in a (n - 2) \times (n - 2) grid (for n \geq 3), and that no grid smaller than (2n/3 - 1) \times (2n/3 - 1) can be used for this purpose, if n is a multiple of 3. In fact, it can be shown that, for all n \geq 3,each dimension of the resulting grid needs to be at least [2(n - 1)/3], even if the other one is allowed to be infinite. In this paper we show that this bound is tight, by presenting a grid drawing algorithm that produces drawings of width [2(n - 1)/3]. The height of the produced drawings is bounded by 4[2(n - 1)/3] - 1.
Repository Staff Only: item control page References |