2-Connecting outerplanar graphs without blowing up the pathwidth

Given a connected outerplanar graph G of pathwidth p, we give an algorithm to add edges to G to get a supergraph of G, which is 2-vertex-connected, outerplanar and of pathwidth O ( p ). This settles an open problem raised by Biedl [1], in the context of computing minimum height planar straight line drawings of outerplanar graphs, with their vertices placed on a two-dimensional grid. In conjunction with the result of this paper, the constant factor approximation algorithm for this problem obtained by Biedl [1] for 2-vertex-connected outerplanar graphs will work for all outer planar graphs.

Authors

• Jasine Babu
• Manu Basavaraju
• L. Sunil Chandran
• Deepak Rajendraprasad

Keywords

• Pathwidth
• Outerplanar graph
• 2-Vertex-connected