Minimum-Width Grid Drawings of Plane Graphs (Extended Abstract)
Chrobak, Marek and Nakano, Shin-Ichi (1995) Minimum-Width Grid Drawings of Plane Graphs (Extended Abstract). In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994, Princeton, New Jersey, USA , pp. 104-110 (Official URL: http://dx.doi.org/10.1007/3-540-58950-3_361).
Full text not available from this repository.
Given 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