Splitting plane graphs to outerplanarity

DOI10.1007/978-3-031-27051-2_19arXiv2301.09440MaRDI QIDQ6091165

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

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 setvertex splittingouterplanarity

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A \(13k\)-kernel for planar feedback vertex set via region decomposition
• On triangulating \(k\)-outerplanar graphs
• Small drawings of outerplanar graphs, series-parallel graphs, and other planar graphs
• Minimum size of feedback vertex sets of planar graphs of girth at least five
• The splitting number of complete bipartite graphs
• Three ways to cover a graph
• The toroidal splitting number of the complete graph \(K_ n\)
• The splitting number of the complete graph in the projective plane
• On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
• The book thickness of a graph
• The node-deletion problem for hereditary properties is NP-complete
• A partial k-arboretum of graphs with bounded treewidth
• On the edge-length ratio of outerplanar graphs
• On the planar split thickness of graphs
• The splitting number of the complete graph
• Face covers and the genus problem for apex graphs
• Cluster graph modification problems
• A new bound on the feedback vertex sets in cubic graphs
• Searching among intervals and compact routing tables
• Connecting face hitting sets in planar graphs
• Planar rectilinear drawings of outerplanar graphs in linear time
• Obtaining a planar graph by vertex deletion
• Approximation of pathwidth of outerplanar graphs
• On double and multiple interval graphs
• Lower Bounds For Induced Forests in Cubic Graphs
• On the Complexity of Covering Vertices by Faces in a Planar Graph
• Approximation algorithms for NP-complete problems on planar graphs
• Augmenting Outerplanar Graphs
• VERTEX SPLITTING IN DAGS AND APPLICATIONS TO PARTIAL SCAN DESIGNS AND LOSSY CIRCUITS
• Node-and edge-deletion NP-complete problems
• SPLITTING NUMBER is NP-complete
• Complexity classification of some edge modification problems
• Planarizing graphs and their drawings by vertex splitting
• An FPT algorithm for bipartite vertex splitting