Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
438169 | Theoretical Computer Science | 2014 | 16 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jasine Babu, Manu Basavaraju, L. Sunil Chandran, Deepak Rajendraprasad,