Bend-optimal orthogonal drawings of triconnected plane graphs. Issue 2 (1st August 2018)

• Record Type: Journal Article
• Authors: Bhatia, Siddharth; Lad, Kunal; Kumar, Rajiv
• Is Part Of: AKCE International Journal of Graphs and Combinatorics. Volume 15:Issue 2(2018)
• Page Start: 168
• Page End: 173
• Publication Date: 2018-08-01
• Subjects: Orthogonal drawing -- Triconnected plane graphs -- Bend optimal drawing
• DOI: 10.1016/j.akcej.2017.08.001
• Languages: English
• ISSNs: 0972-8600

Abstract

Abstract: A drawing of a plane graph G 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 O ( n 1 . 5 ) where n 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 k of degree-4 vertices in the graph) in the resulting drawing with respect to the number b ( G ) of bends in the bend-optimal orthogonal drawing of the same graph. The bound is b ( G ) + 3 k .