2-Connecting outerplanar graphs without blowing up the pathwidth
Data(s) |
2014
|
---|---|
Resumo |
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. (C) 2014 Elsevier B.V. All rights reserved. |
Formato |
application/pdf |
Identificador |
http://eprints.iisc.ernet.in/50331/1/the_com_sci_554_119_2014.pdf Babu, Jasine and Basavaraju, Manu and Chandran, Sunil L and Rajendraprasad, Deepak (2014) 2-Connecting outerplanar graphs without blowing up the pathwidth. In: 19th Annual International Computing and Combinatorics Conference (COCOON, JUN, 2013, Hanhzhou, PEOPLES R CHINA, pp. 119-134. |
Publicador |
ELSEVIER SCIENCE BV |
Relação |
http://dx.doi.org/ 10.1016/j.tcs.2014.04.032 http://eprints.iisc.ernet.in/50331/ |
Palavras-Chave | #Computer Science & Automation (Formerly, School of Automation) |
Tipo |
Conference Proceedings NonPeerReviewed |