Computing β-Drawings of 2-Outerplane Graphs in Linear Time (Extended Abstract)
Mohammad Irfan, Md. Saidur Rahman · 2008
A straight-line drawing of a plane graph G is a drawing of G where each vertex is drawn as a point and each edge is drawn as a straight-line segment without edge crossings. A drawing Γ of a plane graph G is a straight- line drawing of G with the additional geometric constraint that two vertices of G are adjacent if and only if no other vertex of G is drawn in Γ within a proximity of these two vertices in Γ . Depending upon how the region is defined, a given plane graph G may or may not admit a drawing. In one class of drawings, known as β-drawings, the region is defined in terms of a parameter β ,w hereβ ∈ (0, ∞). A plane graph G is β-drawable if G admits a β-drawing. A sufficient condition for a biconnected 2-outerplane graph G to have a β-drawing is known. However, the known algo- rithm for testing the sufficient condition takes time O(n 2 ). In this paper, we give a linear-time algorithm to test whether a biconnected 2-outerplane graph G sat- isfies the known sufficient condition or not. This consequently leads to a linear algorithm for β-drawing of a wide subclass of biconnected 2-outerplane graphs.