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", }
Christoph Doppelbauer | 10.05.2024