Geodesic
Splitting Plane Graphs to Outerplanarity
Journal of Graph Algorithms and Applications, Special issue on Selected Papers from the 17th International Conference and Workshops on Algorithms and Computation, WALCOM 2023 , Tome 28 (2024) no. 3, pp. 31-48.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.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.
DOI : 10.7155/jgaa.v28i3.2970
Keywords: vertex splitting, outerplanarity, feedback vertex set

Martin Gronemann 1 ; Martin Nöllenburg 1 ; Anaïs Villedieu 1

1 TU Wien 
@article{JGAA_2024_28_3_a3,
     author = {Martin Gronemann and Martin N\"ollenburg and Ana{\"\i}s Villedieu},
     title = {Splitting {Plane} {Graphs} to {Outerplanarity}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {31--48},
     publisher = {mathdoc},
     volume = {28},
     number = {3},
     year = {2024},
     doi = {10.7155/jgaa.v28i3.2970},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i3.2970/}
}
TY  - JOUR
AU  - Martin Gronemann
AU  - Martin Nöllenburg
AU  - Anaïs Villedieu
TI  - Splitting Plane Graphs to Outerplanarity
JO  - Journal of Graph Algorithms and Applications
PY  - 2024
SP  - 31
EP  - 48
VL  - 28
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i3.2970/
DO  - 10.7155/jgaa.v28i3.2970
LA  - en
ID  - JGAA_2024_28_3_a3
ER  - 
%0 Journal Article
%A Martin Gronemann
%A Martin Nöllenburg
%A Anaïs Villedieu
%T Splitting Plane Graphs to Outerplanarity
%J Journal of Graph Algorithms and Applications
%D 2024
%P 31-48
%V 28
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i3.2970/
%R 10.7155/jgaa.v28i3.2970
%G en
%F JGAA_2024_28_3_a3
Martin Gronemann; Martin Nöllenburg; Anaïs Villedieu. Splitting Plane Graphs to Outerplanarity. Journal of Graph Algorithms and Applications, 
							Special issue on  Selected Papers from the 17th International Conference and Workshops on Algorithms and Computation, WALCOM 2023
					, Tome 28 (2024) no. 3, pp. 31-48. doi : 10.7155/jgaa.v28i3.2970. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i3.2970/

Cité par Sources :