Cubicity, boxicity, and vertex cover
From MaRDI portal
Publication:1025509
DOI10.1016/j.disc.2008.06.003zbMath1184.05094arXiv0712.2688OpenAlexW2134744951MaRDI QIDQ1025509
Anita Das, Chintan D. Shah, L. Sunil Chandran
Publication date: 19 June 2009
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0712.2688
Related Items
Ferrers dimension of grid intersection graphs ⋮ Boxicity of line graphs ⋮ Cubicity and bandwidth ⋮ Sublinear approximation algorithms for boxicity and related problems ⋮ Boxicity of circular arc graphs ⋮ Boxicity and cubicity of asteroidal triple free graphs ⋮ A constant factor approximation algorithm for boxicity of circular arc graphs ⋮ Bounds for the boxicity of Mycielski graphs ⋮ Boxicity and cubicity of product graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Computing the boxicity of a graph by covering its complement by cointerval graphs
- Geometric representation of graphs in low dimension using axis parallel boxes
- The cubicity of hypercube graphs
- On the cubicity of certain graphs
- Interval representations of planar graphs
- Sphericity exceeds cubicity for almost all complete bipartite graphs
- A characterization of Robert's inequality for boxicity
- A special planar satisfiability problem and a consequence of its NP- completeness
- Boxicity and maximum degree
- Sphericity, cubicity, and edge clique covers of graphs
- Boxicity and treewidth
- The Complexity of the Partial Order Dimension Problem
- Reducibility among Combinatorial Problems
- Sphere-of-influence graphs using the sup-norm
