Splitting plane graphs to outerplanarity

DOI10.1007/978-3-031-27051-2_19MaRDI QIDQ6091165zbMATH OpenFDO

Authors Martin Gronemann, Martin Nöllenburg, Anaïs Villedieu

Publication date 24 November 2023

Published in WALCOM: Algorithms and Computation (Search for Journal in Brave)

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

zbMATH Keywords

feedback vertex setouterplanarityvertex splitting

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

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.

Cites work

• A 13k-kernel for planar feedback vertex set via region decomposition
• A new bound on the feedback vertex sets in cubic graphs
• A partial k-arboretum of graphs with bounded treewidth
• An FPT algorithm for bipartite vertex splitting
• Approximation algorithms for NP-complete problems on planar graphs
• Approximation of pathwidth of outerplanar graphs
• Augmenting Outerplanar Graphs
• Bidimensionality: new connections between FPT algorithms and PTASs
• Cluster graph modification problems
• Complexity classification of some edge modification problems
• Connecting face hitting sets in planar graphs
• Face covers and the genus problem for apex graphs
• scientific article; zbMATH DE number 1189238 (Why is no real title available?)
• scientific article; zbMATH DE number 1522938 (Why is no real title available?)
• Lower Bounds For Induced Forests in Cubic Graphs
• Minimum size of feedback vertex sets of planar graphs of girth at least five
• Node-and edge-deletion NP-complete problems
• Obtaining a planar graph by vertex deletion
• On double and multiple interval graphs
• On the Complexity of Covering Vertices by Faces in a Planar Graph
• On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
• On triangulating \(k\)-outerplanar graphs
• Planar rectilinear drawings of outerplanar graphs in linear time
• Planarizing graphs and their drawings by vertex splitting
• Searching among intervals and compact routing tables
• Small drawings of outerplanar graphs, series-parallel graphs, and other planar graphs
• SPLITTING NUMBER is NP-complete
• The book thickness of a graph
• The node-deletion problem for hereditary properties is NP-complete
• The splitting number of complete bipartite graphs
• The splitting number of the complete graph
• The splitting number of the complete graph in the projective plane
• The toroidal splitting number of the complete graph \(K_ n\)
• Three ways to cover a graph
• Vertex splitting in dags and applications to partial scan designs and lossy circuits

Cited in

(1)

• Planarizing graphs and their drawings by vertex splitting

This page was built for publication: Splitting plane graphs to outerplanarity

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