Geometric representation of graphs in low dimension using axis parallel boxes

DOI10.1007/s00453-008-9163-5zbMath1216.05089OpenAlexW2150795199WikidataQ29039815 ScholiaQ29039815MaRDI QIDQ848956

L. Sunil Chandran, Naveen Sivadasan, Mathew C. Francis

Publication date: 23 February 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-008-9163-5

zbMATH Keywords

randomized algorithmrandom graphderandomizationintersection graphsboxicity

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Geometric representation of graphs in low dimension using axis parallel boxes ⋮ Local boxicity and maximum degree ⋮ Bounding threshold dimension: realizing graphic Boolean functions as the AND of majority gates ⋮ Boxicity of line graphs ⋮ Cubicity and bandwidth ⋮ Separability, boxicity, and partial orders ⋮ Boxicity of leaf powers ⋮ Chordal bipartite graphs with high boxicity ⋮ Boxicity of circular arc graphs ⋮ Boxicity and cubicity of asteroidal triple free graphs ⋮ On the cubicity of bipartite graphs ⋮ Cubicity, degeneracy, and crossing number ⋮ Cubicity, boxicity, and vertex cover ⋮ An upper bound for cubicity in terms of boxicity ⋮ Boxicity of Halin graphs ⋮ On the cubicity of interval graphs

Cites Work

• Grid intersection graphs and boxicity
• Geometric representation of graphs in low dimension using axis parallel boxes
• Interval representations of planar graphs
• Poset boxicity of graphs
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• A note on circular dimension
• The circular dimension of a graph
• Label placement by maximum independent set in rectangles
• A special planar satisfiability problem and a consequence of its NP- completeness
• Treewidth. Computations and approximations
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Boxicity and maximum degree
• Boxicity and treewidth
• Efficient Approximation Algorithms for Tiling and Packing Problems with Rectangles
• The Complexity of the Partial Order Dimension Problem
• Polynomial-time approximation schemes for packing and piercing fat objects
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item