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(n^1.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}, }