Chrobak, Marek and Nakano, Shin-ichi (1995) Minimum-Width Grid Drawings of Plane Graphs (Extended Abstract). [Conference Paper]
Full text not available from this repository.
Abstract
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 |
|---|---|
| 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 |
| ID Code: | 103 |
| Deposited By: | Selbach, Anna |
| Deposited On: | 25 Nov 2004 |
| Last Modified: | 18 Sep 2008 13:08 |
Repository Staff Only: item control page
