Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes

2008/01/23 by L. Sunil Chandran, Mathew C. Francis, Naveen Sivadasan · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Approximation algorithm #Bounded function #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Discrete mathematics #Graph #Independent set #Intersection graph #Interval graph #Line graph #Mathematics #Pathwidth #Time complexity

paper · doi:10.1007/s00453-008-9163-5

openalex publication_date 2008/01/23 · crossref created 2008/01/23 · crossref issued 2008/01/24 · crossref published 2008/01/24 · crossref published-online 2008/01/24 · crossref published-print 2010/02/01 · crossref deposited 2019/05/29 · openalex created_date 2025/10/10 · crossref indexed 2026/05/12 · openalex updated_date 2026/07/29

Citations

• Random Graphs
• Clique is hard to approximate within n/sup 1-ε/
• Interval representations of planar graphs
• Grid intersection graphs and boxicity
• Efficient Approximation Algorithms for Tiling and Packing Problems with Rectangles
• Polynomial-time approximation schemes for packing and piercing fat objects
• Boxicity and treewidth
• The Complexity of the Partial Order Dimension Problem
• Clique is hard to approximate within n1−ε
• A special planar satisfiability problem and a consequence of its NP-completeness
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Label placement by maximum independent set in rectangles

Cited by

• Parameterized Algorithms for Boxicity
• Cubicity, degeneracy, and crossing number
• Boxicity [wikipedia]