Bend-optimal orthogonal drawings of triconnected plane graphs

Abstract

A drawing of a plane graph in which each edge is represented by a sequence of alternating horizontal and vertical line segments is called an orthogonal drawing. The points of intersection of horizontal and vertical line segments of an edge in an orthogonal drawing are called bends. The best known algorithm to find a bend-optimal orthogonal drawing of a plane graph takes time where is the number of vertices in the graph. In this paper we present a new linear time algorithm to find an orthogonal drawing of a plane 3-connected graph (with maximum degree 4) and give bounds on number of bends (in terms of number of degree-4 vertices in the graph) in the resulting drawing with respect to the number of bends in the bend-optimal orthogonal drawing of the same graph. The bound is .

Keywords

• orthogonal drawing
• triconnected plane graphs
• bend optimal drawing