Planarizing graphs and their drawings by vertex splitting

DOI10.1007/978-3-031-22203-0_17arXiv2202.12293MaRDI QIDQ6172199

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

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)

Related Items (3)

Splitting plane graphs to outerplanarity ⋮ Planarizing graphs and their drawings by vertex splitting ⋮ An FPT algorithm for bipartite vertex splitting

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The splitting number of complete bipartite graphs
• Three ways to cover a graph
• A bounded search tree algorithm for parameterized face cover
• The toroidal splitting number of the complete graph \(K_ n\)
• The node-deletion problem for hereditary properties is NP-complete
• On the planar split thickness of graphs
• The splitting number of the complete graph
• Graph minors. XIII: The disjoint paths problem
• Obtaining a planar graph by vertex deletion
• Planarizing Graphs - A Survey and Annotated Bibliography
• On the Complexity of Covering Vertices by Faces in a Planar Graph
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Crossing Numbers of Graphs
• Testing Planarity of Partially Embedded Graphs
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
• Angular Resolutions: Around Vertices and Crossings
• Crossing Layout in Non-planar Graph Drawings
• Planarity Allowing Few Error Vertices in Linear Time
• Parameterized and Exact Computation
• A Near-Optimal Planarization Algorithm
• Parameterized Algorithms
• Inserting one edge into a simple drawing is hard
• SPLITTING NUMBER is NP-complete
• Planarizing graphs and their drawings by vertex splitting

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