Planar Biconnectivity Augmentation with Fixed Embedding
| Autor: | Carsten Gutwenger, Bernd Zey, Petra Mutzel |
|---|---|
| Rok vydání: | 2009 |
| Předmět: | |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783642102165 IWOCA |
| DOI: | 10.1007/978-3-642-10217-2_29 |
| Popis: | A combinatorial embedding ${\it \Pi}$ of a planar graph G = (V,E) is defined by the cyclic order of incident edges around each vertex in a planar drawing of G. The planar biconnectivity augmentation problem with fixed embedding (PBA-Fix) asks for a minimum edge set E? ? V×V that augments ${\it \Pi}$ to a combinatorial embedding ${\it \Pi}'$ of G + E? such that G + E? is biconnected and ${\it \Pi}$ is preserved, i.e., ${\it \Pi}'$ restricted to G yields again ${\it \Pi}$. In this paper, we show that PBA-Fix is NP-hard in general, i.e., for not necessarily connected graphs, by giving a reduction from 3-PARTITION. For connected graphs, we present an $\mathcal{O}(|V|(1+\alpha(|V|)))$ time algorithm solving PBA-Fix optimally. Moreover, we show that--considering each face of ${\it \Pi}$ separately--this algorithm meets the lower bound for the general biconnectivity augmentation problem proven by Eswaran and Tarjan [1]. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|