A Linear-Time Algorithm for Bend-Optimal Orthogonal Drawings of Biconnected Cubic Plane Graphs (Extended Abstract)

Nakano, Shin-Ichi and Yoshikawa, Makiko (2001) A Linear-Time Algorithm for Bend-Optimal Orthogonal Drawings of Biconnected Cubic Plane Graphs (Extended Abstract). In: Graph Drawing 8th International Symposium, GD 2000, September 20–23, 2000 , pp. 296-307(Official URL: http://dx.doi.org/10.1007/3-540-44541-2_28).

Full text not available from this repository.

Abstract

An orthogonal drawing of a plane graph G is a drawing of G with the given planar embedding in which each vertex is mapped to a point, each edge is drawn as a sequence of alternate horizontal and vertical line segments, and any two edges do not cross except at their common end. Observe that only a planar graph with the maximum degree four or less has an orthogonal drawing. The best known algorithm to find an orthogonal drawing runs in time $O(n^{7/4}\sqrt {\log n})$ for any plane graph with n vertices. In this paper we give a linear-time algorithm to find an orthogonal drawing of a given biconnected cubic plane graph with the minimum number of bends.

Item Type:	Conference Paper
Additional Information:	10.1007/3-540-44541-2_28
Classifications:	G Algorithms and Complexity > G.999 Others G Algorithms and Complexity > G.210 Bends P Styles > P.600 Poly-line > P.600.700 Orthogonal
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/408

Actions (login required)

View Item