Planarizing graphs and their drawings by vertex splitting

DOI10.1007/978-3-031-22203-0_17MaRDI QIDQ6172199zbMATH OpenFDO

Authors Martin Nöllenburg, Manuel Sorge, Soeren Terziadis, Anaïs Villedieu, Hsiang-Yun Wu, Jules Wulms

Publication date 16 August 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2202.12293

zbMATH Keywords

parameterized complexityplanarizationvertex splitting

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

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 $vinV$, introduces two new vertices $v_1,v_2$, and distributes the edges formerly incident to $v$ among its two split copies $v_1,v_2$. The splitting number problem is known to be NP-complete. In this paper we shift focus to the splitting number of graph drawings in $mathbb{R}^2$, where the new vertices resulting from vertex splits can be re-embedded into the existing drawing of the remaining graph. We first provide a non-uniform fixed-parameter tractable (FPT) algorithm for the splitting number problem (without drawings). Then we show the NP-completeness of the splitting number problem for graph drawings, 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.

Recommendations

• Partitioning Planar Graphs
• An edge-splitting algorithm in planar graphs
• Splitting plane graphs to outerplanarity
• On the planar subdivision of a drawing of a complete graph in the plane
• On cleaving a planar graph
• Subdivisions in planar graphs
• Planar graphs: Theory and algorithms
• On drawings and decompositions of 1-planar graphs
• scientific article; zbMATH DE number 475620
• Planarizing graphs---a survey and annotated bibliography

Cites work

• A bounded search tree algorithm for parameterized face cover
• A near-optimal planarization algorithm
• Angular Resolutions: Around Vertices and Crossings
• Crossing Layout in Non-planar Graph Drawings
• Crossing numbers of graphs
• Graph minors. XIII: The disjoint paths problem
• scientific article; zbMATH DE number 1953101 (Why is no real title available?)
• scientific article; zbMATH DE number 7559402 (Why is no real title available?)
• Inserting a vertex into a planar graph
• Inserting multiple edges into a planar graph
• Inserting one edge into a simple drawing is hard
• Obtaining a planar graph by vertex deletion
• On the Complexity of Covering Vertices by Faces in a Planar Graph
• Parameterized algorithms
• Parameterized and Exact Computation
• Planarity Allowing Few Error Vertices in Linear Time
• Planarizing graphs and their drawings by vertex splitting
• Planarizing graphs---a survey and annotated bibliography
• SPLITTING NUMBER is NP-complete
• Testing Planarity of Partially Embedded Graphs
• The node-deletion problem for hereditary properties is NP-complete
• The Rectilinear Steiner Tree Problem is NP-Complete
• The splitting number of complete bipartite graphs
• The splitting number of the complete graph
• The toroidal splitting number of the complete graph \(K_ n\)
• Three ways to cover a graph

Cited in

(17)

• Subdivisions in planar graphs
• Obtaining a planar graph by vertex deletion
• On Representation of Planar Graphs by Segments
• Hypergraph planarity and the complexity of drawing venn diagrams
• scientific article; zbMATH DE number 1262793 (Why is no real title available?)
• Untangling planar graphs from a specified vertex position-Hard cases
• Drawing HV-Restricted Planar Graphs
• Splitting plane graphs to outerplanarity
• Planarizing graphs and their drawings by vertex splitting
• An FPT algorithm for bipartite vertex splitting
• Parameterized Complexity of Vertex Splitting to Pathwidth at Most 1
• Splitting plane graphs to outerplanarity
• Cluster editing with overlapping communities
• Parameterized algorithms for planar 2-layer drawing by vertex splitting on a given subset
• The complexity of cluster vertex splitting and company
• On the complexity of establishing hereditary graph properties via vertex splitting
• A unified FPT framework for crossing number problems

This page was built for publication: Planarizing graphs and their drawings by vertex splitting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6172199)