A Linear Algorithm for Optimal Orthogonal Drawings of Triconnected Cubic Plane Graphs

Rahman, Md. Saidur and Nakano, Shin-Ichi and Nishizeki, Takao (1998) A Linear Algorithm for Optimal Orthogonal Drawings of Triconnected Cubic Plane Graphs. In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997 , pp. 99-110(Official URL: http://dx.doi.org/10.1007/3-540-63938-1_54).

Full text not available from this repository.

Abstract

An orthogonal drawing of a plane graph G is a drawing of G in which each edge is drawn as a sequence of alternate horizontal and vertical line segments. In this paper we give a linear-time algorithm to find an orthogonal drawing of a given 3-connected cubic plane graph with the minimum number of bends. The best known algorithm takes time O(n^{7/4} \sqrt {log n}) for any plane graph of n vertices.

Item Type:	Conference Paper
Additional Information:	10.1007/3-540-63938-1_54
Classifications:	G Algorithms and Complexity > G.210 Bends P Styles > P.600 Poly-line > P.600.700 Orthogonal G Algorithms and Complexity > G.560 Geometry
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/172

Actions (login required)

View Item