On the planar split thickness of graphs

DOI10.1007/s00453-017-0328-yzbMath1390.68498arXiv1512.04839OpenAlexW3101895193WikidataQ62042369 ScholiaQ62042369MaRDI QIDQ1742373

Hamideh Vosoughpour, David Eppstein, Anna Lubiw, Giuseppe Liotta, Philipp Kindermann, Debajyoti Mondal, Aude Maignan, Stephen G. Kobourov, Stephen K. Wismath, S. H. Whitesides

Publication date: 11 April 2018

Published in: Algorithmica, LATIN 2016: Theoretical Informatics (Search for Journal in Brave)

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

zbMATH Keywords

thicknessapproximationgraph theoryplanaritycomplete graphsgraph drawingNP-hardnessfixed-parameter tractablegenus-1 graphssplittable

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth, Fan-crossing free graphs and their relationship to other beyond-planar graphs, \((k,p)\)-planarity: a relaxation of hybrid planarity, Splits with forbidden subgraphs, Splitting plane graphs to outerplanarity, Upper bounds for bar visibility of subgraphs and \(n\)-vertex graphs, Planarizing graphs and their drawings by vertex splitting, An FPT algorithm for bipartite vertex splitting, Efficient generation of different topological representations of graphs beyond-planarity, Efficient Generation of Different Topological Representations of Graphs Beyond-Planarity, Parameterized Leaf Power Recognition via Embedding into Graph Products, On the planar split thickness of graphs, On the Bar Visibility Number of Complete Bipartite Graphs, Parameterized leaf power recognition via embedding into graph products

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The interval number of a planar graph: Three intervals suffice
• A simplified NP-complete satisfiability problem
• The splitting number of complete bipartite graphs
• Three ways to cover a graph
• The toroidal splitting number of the complete graph \(K_ n\)
• Enumeration of projective-planar embeddings of graphs
• The splitting number of the complete graph in the projective plane
• The spherical genus and virtually planar graphs
• Forests, frames, and games: Algorithms for matroid sums and applications
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• On the planar split thickness of graphs
• The splitting number of the complete graph
• The extremal function for complete minors
• How not to characterize planar-emulable graphs
• Graph treewidth and geometric thickness parameters
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Planarizing Graphs - A Survey and Annotated Bibliography
• Planar Induced Subgraphs of Sparse Graphs
• Noncrossing Subgraphs in Topological Layouts
• Solution of Heawood's empire problem in the plane.
• A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory
• Coloring Ordinary Maps, Maps of Empires, and Maps of the Moon
• The geometric thickness of low degree graphs
• The Thickness of the Complete Graph
• Decomposition of Finite Graphs Into Forests
• SPLITTING NUMBER is NP-complete