Record link: 
http://hdl.handle.net/20.500.12708/190037
-
Title: 
Splitting Plane Graphs to Outerplanarity
en
Citation: 
Gronemann, M., Nöllenburg, M., & Villedieu, A. (2023). Splitting Plane Graphs to Outerplanarity. In C.-C. Lin, B. M. T. Lin, & G. Liotta (Eds.), WALCOM: Algorithms and Computation : 17th International Conference and Workshops, WALCOM 2023, Hsinchu, Taiwan, March 22–24, 2023, Proceedings (pp. 217–228). Springer. https://doi.org/10.1007/978-3-031-27051-2_19
-
Publisher DOI: 
10.1007/978-3-031-27051-2_19
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Language: 
English
-
Authors: 
Gronemann, Martin 
Nöllenburg, Martin 
Villedieu, Anaïs 
-
Organisational Unit: 
E192-01 - Forschungsbereich Algorithms and Complexity 
-
Published in: 
WALCOM: Algorithms and Computation : 17th International Conference and Workshops, WALCOM 2023, Hsinchu, Taiwan, March 22–24, 2023, Proceedings 
-
ISBN: 
978-3-031-27051-2
-
Volume: 
13973
-
DOI of the book: 
10.1007/978-3-031-27051-2
-
Date (published): 
2023
-
Event name: 
17th International Conference and Workshops on Algorithms and Computation (WALCOM 2023) 
en
Event date: 
22-Mar-2023 - 24-Mar-2023
-
Event place: 
Hsinchu, Taiwan (Province of China)
-
Number of Pages: 
12
-
Publisher: 
Springer, Cham
-
Peer reviewed: 
Yes
-
Keywords: 
Feedback vertex set; Outerplanarity; Vertex splitting
en
Abstract: 
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. Finally, we provide upper and lower bounds for certain families of maximal planar graphs.
en
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
1020 - Informatik: 80%
1010 - Mathematik: 20%
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

92
checked on Dec 1, 2023

Google ScholarTM

Check