Approximation Algorithms for Geometric Intersection Graphs

DOI10.1007/978-3-540-74839-7_15zbMath1141.68536OpenAlexW2136451944MaRDI QIDQ3508563

Klaus Jansen

Publication date: 1 July 2008

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-74839-7_15

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Unnamed Item
• MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
• Unit disk graphs
• Some simplified NP-complete graph problems
• Label placement by maximum independent set in rectangles
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Approximation algorithms for NP-complete problems on planar graphs
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Simple heuristics for unit disk graphs
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
• Representing graphs by disks and balls (a survey of recognition-complexity results)