Veröffentlichung

Titel:
Regular augmentation of planar graphs
AutorInnen:
Tanja Hartmann
Jonathan Rollin
Ignaz Rutter
Kategorie:
Artikel in Zeitschriften
erschienen in:
Algorithmica, Vol. 73, No. 2, pp. 1–65, 2015
Abstract:

In this paper, we study the problem of augmenting a planar graph such that it becomes k-regular, c-connected and remains planar, either in the sense that the augmented graph is planar, or in the sense that the input graph has a fixed (topological) planar embedding that can be extended to a planar embedding of the augmented graph. We fully classify the complexity of this problem for all values of k and c in both, the variable embedding and the fixed embedding case. For k≤2 all problems are simple and for k≥4 all problems are NP-complete. Our main results are efficient algorithms (with running time O(n1.5)) for deciding the existence of a c-connected, 3-regular augmentation of a graph with a fixed planar embedding for c=0,1,2 and a corresponding hardness result for c=3. The algorithms are such that for yes-instances a corresponding augmentation can be constructed in the same running time.

Download:
Journal Website
BibTeX-Eintrag:
@article{, author = {Tanja Hartmann and Jonathan Rollin and Ignaz Rutter}, title = {Regular Augmentation of Planar Graphs}, journal = {Algorithmica}, volume = {73}, number = {2}, pages = {306--370}, year = {2015}, }
Christoph Doppelbauer | 10.05.2024