TY - JOUR
AU - Gronemann, Martin
AU - Nöllenburg, Martin
AU - Villedieu, Anaïs
PY - 2024/09/10
Y2 - 2024/10/05
TI - Splitting Plane Graphs to Outerplanarity
JF - Journal of Graph Algorithms and Applications
JA - JGAA
VL - 28
IS - 3
SE -
DO - 10.7155/jgaa.v28i3.2970
UR - https://jgaa.info/index.php/jgaa/article/view/2970
SP - 31-48
AB - <p>Vertex splitting replaces a vertex by two copies and partitions its incident edges amongst the copies. This problem has been studied as a graph editing operation to achieve desired properties with as few splits as possible, most often planarity, for which the problem is NP-hard.<br />Here we study how to minimize the number of splits to turn a plane graph into an outerplane one. We tackle this problem by establishing a direct connection between splitting a plane graph to outerplanarity, finding a connected face cover, and finding a feedback vertex set in its dual. We prove NP-completeness for plane biconnected graphs, while we show that a polynomial-time algorithm exists for maximal planar graphs. Additionally, we show upper and lower bounds for certain families of maximal planar graphs. Finally, we provide a SAT formulation for the problem, and evaluate it on a small benchmark.</p>
ER -