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 , pp. 104-110(Official URL:

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.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-58950-3_361
Classifications: G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.070 Area / Edge Length
M Methods > M.600 Planar
P Styles > P.999 Others
P Styles > P.540 Planar

Actions (login required)

View Item View Item