Planarizing Graphs and Their Drawings by Vertex Splitting

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

• Entry in reposiTUm (TU Wien Publication Database)
• DOI: 10.1007/978-3-031-22203-0_17

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/",
}