MinimumWidth Grid Drawings of Plane Graphs (Extended Abstract)Chrobak, Marek and Nakano, ShinIchi (1995) MinimumWidth Grid Drawings of Plane Graphs (Extended Abstract). In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994 , pp. 104110(Official URL: http://dx.doi.org/10.1007/3540589503_361). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540589503_361
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 straightline 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.
Actions (login required)
