A Linear Algorithm for Optimal Orthogonal Drawings of Triconnected Cubic Plane GraphsRahman, Md. Saidur and Nakano, ShinIchi 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 1820, 1997 , pp. 99110(Official URL: http://dx.doi.org/10.1007/3540639381_54). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540639381_54
AbstractAn 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 lineartime algorithm to find an orthogonal drawing of a given 3connected 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.
Actions (login required)
