Approximation Algorithms for Independent Sets in Map Graphs

DOI10.1006/jagm.2001.1178zbMath1002.68111OpenAlexW2083807544MaRDI QIDQ2765954

Zhi-Zhong Chen

Publication date: 1 August 2002

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jagm.2001.1178

zbMATH Keywords

planar graphpolynomial-time approximation algorithmsmap graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (23)

Graph separators: A parameterized view ⋮ Tree densities in sparse graph classes ⋮ Map graphs having witnesses of large girth ⋮ \(K_7\)-minors in optimal 1-planar graphs ⋮ Proper 1-immersions of graphs triangulating the plane ⋮ Structure of Graphs with Locally Restricted Crossings ⋮ All 2-planar graphs having the same spanning subgraph ⋮ Clique-based separators for geometric intersection graphs ⋮ Stack and Queue Layouts via Layered Separators ⋮ Recognizing map graphs of bounded treewidth ⋮ Orthogonal Tree Decompositions of Graphs ⋮ Minimal non-1-planar graphs ⋮ Characterizing 5-map graphs by 2-fan-crossing graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing ⋮ Planar graphs having no proper 2-immersions in the plane. I ⋮ Covering and packing of rectilinear subdivision ⋮ Hardness and structural results for half-squares of restricted tree convex bipartite graphs ⋮ Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction ⋮ Decomposition of Map Graphs with Applications. ⋮ Large independent sets in random regular graphs ⋮ Unnamed Item

This page was built for publication: Approximation Algorithms for Independent Sets in Map Graphs