Map graphs

DOI10.1145/506147.506148zbMath1323.05039OpenAlexW2294414813MaRDI QIDQ3196637

Zhi-Zhong Chen, Christos H. Papadimitriou, Michelangelo Grigni

Publication date: 30 October 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/506147.506148

zbMATH Keywords

mapstopological inferencemap graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (36)

Graph separators: A parameterized view ⋮ Clustered 3-colouring graphs of bounded degree ⋮ Rainbow independent sets on dense graph classes ⋮ Tree densities in sparse graph classes ⋮ 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 ⋮ Proper 1-immersions of graphs triangulating the plane ⋮ Structure of Graphs with Locally Restricted Crossings ⋮ Book embeddings of \(k\)-framed graphs and \(k\)-map graphs ⋮ All 2-planar graphs having the same spanning subgraph ⋮ Clique-based separators for geometric intersection graphs ⋮ Stack and Queue Layouts via Layered Separators ⋮ 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 ⋮ Orthogonal Tree Decompositions of Graphs ⋮ Characterizing and recognizing 4-map graphs ⋮ On partitioning the edges of 1-plane graphs ⋮ Ant colony optimization for finding medians of weighted graphs ⋮ Characterizing 5-map graphs by 2-fan-crossing graphs ⋮ Unnamed Item ⋮ On low rank-width colorings ⋮ Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing ⋮ On Aligned Bar 1-Visibility Graphs ⋮ Planar graphs having no proper 2-immersions in the plane. I ⋮ Covering and packing of rectilinear subdivision ⋮ Better bounds for poset dimension and boxicity ⋮ Hardness and structural results for half-squares of restricted tree convex bipartite graphs ⋮ Notes on graph product structure theory ⋮ Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction ⋮ Decomposition of Map Graphs with Applications. ⋮ Unnamed Item

This page was built for publication: Map graphs