A Linear Algorithm for Bend-Optimal Orthogonal Drawings of Triconnected Cubic Plane Graphs
Md. Saidur Rahman, Shin-ichi Nakano, Takao Nishizeki · Journal of Graph Algorithms and Applications · 1999
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 previously known algorithm takes time O(n 7/4 # log n) for any plane graph with n vertices. Communicated by Giuseppe Di Battista and Petra Mutzel. Submitted: March 1998. Revised: November 1998 and March 1999. M. S. Rahman et al., Orthogonal Drawings, JGAA, 3(4) 31--62 (1999) 32 1 Introduction An orthogonal drawing of a plane graph G is a drawing of G with the given 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. Orthogonal drawings have attracted much attention due to their numerous practical applications in circuit schematics...