Recognizing hole-free 4-map graphs in cubic time
From MaRDI portal
Publication:2498931
DOI10.1007/s00453-005-1184-8zbMath1095.68076OpenAlexW2037591624MaRDI QIDQ2498931
Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou
Publication date: 11 August 2006
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-005-1184-8
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (21)
Map graphs having witnesses of large girth ⋮ Recognizing IC-Planar and NIC-Planar Graphs ⋮ Linear-time recognition of map graphs with outerplanar witness ⋮ An annotated bibliography on 1-planarity ⋮ \(\mathsf{NIC}\)-planar graphs ⋮ Improved product structure for graphs on surfaces ⋮ Straight-line drawings of 1-planar graphs ⋮ Book embeddings of \(k\)-framed graphs and \(k\)-map graphs ⋮ Graph product structure for non-minor-closed classes ⋮ Optimal 1-planar multigraphs ⋮ Recognizing map graphs of bounded treewidth ⋮ Recognizing optimal 1-planar graphs in linear time ⋮ \(\mathsf{T}\)-shape visibility representations of 1-planar graphs ⋮ Characterizing and recognizing 4-map graphs ⋮ Embedding-preserving rectangle visibility representations of nonplanar graphs ⋮ Characterizing 5-map graphs by 2-fan-crossing graphs ⋮ Unnamed Item ⋮ On Aligned Bar 1-Visibility Graphs ⋮ Decomposition of Map Graphs with Applications. ⋮ $$\textit{\textbf{k}}$$-Planar Graphs ⋮ IC-Planar Graphs Are 6-Choosable
This page was built for publication: Recognizing hole-free 4-map graphs in cubic time
