## Information

- Publication Type: Conference Paper
- Workgroup(s)/Project(s): not specified
- Date: 2023
- ISBN: 978-3-031-22203-0
- Publisher: Springer
- Location: Tokyo
- Lecturer: Anaïs Villedieu
- Event: International Symposium on Graph Drawing and Network Visualization (GD 2022)
- DOI: 10.1007/978-3-031-22203-0_17
- Booktitle: Graph Drawing and Network Visualization. GD 2022
- Pages: 15
- Volume: 13764
- Conference date: 13. September 2022 – 16. September 2022
- Pages: 232 – 246
- Keywords: Parameterized complexity, Planarization, Vertex splitting

## Abstract

The splitting number of a graph G= (V, E) is the minimum number of vertex splits required to turn G into a planar graph, where a vertex split removes a vertex v∈ V, introduces two new vertices v1, v2, and distributes the edges formerly incident to v among v1, v2. The splitting number problem is known to be NP-complete for abstract graphs and we provide a non-uniform fixed-parameter tractable (FPT) algorithm for this problem. We then shift focus to the splitting number of a given topological graph drawing in R2, where the new vertices resulting from vertex splits must be re-embedded into the existing drawing of the remaining graph. We show NP-completeness of this embedded splitting number problem, even for its two subproblems of (1) selecting a minimum subset of vertices to split and (2) for re-embedding a minimum number of copies of a given set of vertices. For the latter problem we present an FPT algorithm parameterized by the number of vertex splits. This algorithm reduces to a bounded outerplanarity case and uses an intricate dynamic program on a sphere-cut decomposition.## Additional Files and Images

## Weblinks

## BibTeX

@inproceedings{noellenburg-2023-pga, title = "Planarizing Graphs and Their Drawings by Vertex Splitting", author = "Martin N\"{o}llenburg and Manuel Sorge and Soeren Terziadis and Anaïs Villedieu and Hsiang-Yun Wu and Jules Wulms", year = "2023", abstract = "The splitting number of a graph G= (V, E) is the minimum number of vertex splits required to turn G into a planar graph, where a vertex split removes a vertex v∈ V, introduces two new vertices v1, v2, and distributes the edges formerly incident to v among v1, v2. The splitting number problem is known to be NP-complete for abstract graphs and we provide a non-uniform fixed-parameter tractable (FPT) algorithm for this problem. We then shift focus to the splitting number of a given topological graph drawing in R2, where the new vertices resulting from vertex splits must be re-embedded into the existing drawing of the remaining graph. We show NP-completeness of this embedded splitting number problem, even for its two subproblems of (1) selecting a minimum subset of vertices to split and (2) for re-embedding a minimum number of copies of a given set of vertices. For the latter problem we present an FPT algorithm parameterized by the number of vertex splits. This algorithm reduces to a bounded outerplanarity case and uses an intricate dynamic program on a sphere-cut decomposition.", isbn = "978-3-031-22203-0", publisher = "Springer", location = "Tokyo", event = "International Symposium on Graph Drawing and Network Visualization (GD 2022)", doi = "10.1007/978-3-031-22203-0_17", booktitle = "Graph Drawing and Network Visualization. GD 2022", pages = "15", volume = "13764", pages = "232--246", keywords = "Parameterized complexity, Planarization, Vertex splitting", URL = "https://www.cg.tuwien.ac.at/research/publications/2023/noellenburg-2023-pga/", }