Article ID Journal Published Year Pages File Type
438169 Theoretical Computer Science 2014 16 Pages PDF
Abstract

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)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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , ,