Veröffentlichung

Titel:

Cubic augmentation of planar graphs

AutorInnen:

Tanja Hartmann
Jonathan Rollin
Ignaz Rutter

Kategorie:

Konferenzbandbeiträge

erschienen in:

Proceedings of the International Symposium on Algorithms and Computation (ISAAC 2012), pp. 402–412

Abstract:

In this paper we study the problem of augmenting a planar graph such that it becomes 3-regular and remains planar. We show that it is NP-hard to decide whether such an augmentation exists. On the other hand, we give an efficient algorithm for the variant of the problem where the input graph has a fixed planar (topological) embedding that has to be preserved by the augmentation. We further generalize this algorithm to test efficiently whether a 3-regular planar augmentation exists that additionally makes the input graph connected or biconnected.

Download:

arXiv

BibTeX-Eintrag:

@InProceedings{, author="Hartmann, Tanja and Rollin, Jonathan and Rutter, Ignaz", editor="Chao, Kun-Mao and Hsu, Tsan-sheng and Lee, Der-Tsai", title="Cubic Augmentation of Planar Graphs", booktitle="ISAAC 2012: Algorithms and Computation", year="2012", publisher="Springer Berlin Heidelberg", address="Berlin, Heidelberg", pages="402--412", }