Map graphs
From MaRDI portal
Publication:3196637
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
Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10)
Related Items
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
