Grid Drawings of Four-Connected Plane Graphs

Miura, Kazuyuki and Nakano, Shin-Ichi and Nishizeki, Takao (1999) Grid Drawings of Four-Connected Plane Graphs. In: Graph Drawing 7th International Symposium, GD’99, September 15-19, 1999 , pp. 145-154(Official URL: http://dx.doi.org/10.1007/3-540-46648-7_15).

Full text not available from this repository.

Abstract

A grid drawing of a plane graph G is a drawing of G on the plane so that all vertices of G are put on plane grid points and all edges are drawn as straight line segments between their endpoints without any edge-intersection. In this paper we give a very simple algorithm to find a grid drawing of any given 4-connected plane graph G with four or more vertices on the outer face. The algorithm takes time O(n) and needs a rectangular grid of width \lceil n/2 \rceil - 1 and height \lceil n/2 \rceil if G has n vertices. The algorithm is best possible in the sense that there are an infinite number of 4-connected plane graphs any grid drawings of which need rectangular grids of width \lceil n/2 \rceil - 1 and height \lceil n/2 \rceil.

Item Type:	Conference Paper
Additional Information:	10.1007/3-540-46648-7_15
Classifications:	P Styles > P.720 Straight-line G Algorithms and Complexity > G.070 Area / Edge Length M Methods > M.600 Planar P Styles > P.999 Others P Styles > P.540 Planar
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/304

Actions (login required)

View Item