Lower bounds for boxicity
From MaRDI portal
Publication:2341923
DOI10.1007/s00493-011-2981-0zbMath1340.05193arXiv0806.3175OpenAlexW2092146896MaRDI QIDQ2341923
Abhijin Adiga, Naveen Sivadasan, L. Sunil Chandran
Publication date: 7 May 2015
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0806.3175
Random graphs (graph-theoretic aspects) (05C80) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items
Local boxicity ⋮ Upper bound on cubicity in terms of boxicity for graphs of low chromatic number ⋮ Box representations of embedded graphs ⋮ Boxicity and cubicity of asteroidal triple free graphs ⋮ A note on the intersection property for flat boxes and boxicity in \(\mathbb R^d\) ⋮ On the stab number of rectangle intersection graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Computing the boxicity of a graph by covering its complement by cointerval graphs
- Grid intersection graphs and boxicity
- On the sphericity and cubicity of graphs
- Interval representations of planar graphs
- Embedding of trees in Euclidean spaces
- Poset boxicity of graphs
- Eigenvalues and expanders
- A characterization of Robert's inequality for boxicity
- A note on circular dimension
- Optimal packing and covering in the plane are NP-complete
- Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
- The circular dimension of a graph
- A special planar satisfiability problem and a consequence of its NP- completeness
- Boxicity and maximum degree
- Monotone maps, sphericity and bounded second eigenvalue
- Boxicity and treewidth
- Explicit Concentrators from Generalized N-Gons
- Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
- A proof of alon's second eigenvalue conjecture
- The Complexity of the Partial Order Dimension Problem
- On the chordality of a graph
- A Constant Factor Approximation Algorithm for Boxicity of Circular Arc Graphs
- Probability and Computing
