2011/05/26 by Abhijin Adiga, Adiga, Abhijin, L. Sunil Chandran +3
Computer Science · #05C62 #05C85 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1105.5225
openalex publication_date 2011/05/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
A k-box B=(R1,...,Rk), where each Ri is a closed interval on the real line, is defined to be the Cartesian product R1× R2× ...× Rk. If each Ri is a unit length interval, we call B a k-cube. Boxicity of a graph G, denoted as \boxi(G), is the minimum integer k such that G is an intersection graph of k-boxes. Similarly, the cubicity of G, denoted as \cubi(G), is the minimum integer k such that G is an intersection graph of k-cubes. It was shown in [L. Sunil Chandran, Mathew C. Francis, and Naveen Sivadasan: Representing graphs as the intersection of axis-parallel cubes. MCDES-2008, IISc Centenary Conference, available at CoRR, abs/cs/ 0607092, 2006.] that, for a graph G with maximum degree Δ, \cubi(G)≤ \lceil 4(Δ+1)log n\rceil. In this paper, we show that, for a k-degenerate graph G, \cubi(G) ≤ (k+2) \lceil 2e log n \rceil. Since k is at most Δ and can be much lower, this clearly is a stronger result. This bound is tight. We also give an efficient deterministic algorithm that runs in O(n2k) time to output a 8k(\lceil 2.42 log n\rceil + 1) dimensional cube representation for G. An important consequence of the above result is that if the crossing number of a graph G is t, then \boxi(G) is O(t1/4\lceillog t\rceil3/4) . This bound is tight up to a factor of O((log t)1/4). We also show that, if G has n vertices, then \cubi(G) is O(log n + t1/4log t). Using our bound for the cubicity of k-degenerate graphs we show that cubicity of almost all graphs in G(n,m) model is O(davlog n), where dav denotes the average degree of the graph under consideration.