Header menu link for other important links
X
2-Connecting outerplanar graphs without blowing up the pathwidth
, M. Basavaraju, L.S. Chandran,
Published in Elsevier
2014
Volume: 554
   
Issue: C
Pages: 119 - 134
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). 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. © 2014 Elsevier B.V.
About the journal
JournalData powered by TypesetTheoretical Computer Science
PublisherData powered by TypesetElsevier
ISSN03043975