A Linear Algorithm for Optimal Orthogonal Drawings of Triconnected Cubic Plane GraphsRahman, 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.
Official URL: http://dx.doi.org/10.1007/3-540-63938-1_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 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.
Actions (login required)
|