2006/07/19 by L. Sunil Chandran, Sunil L Chandran, Mathew C. Francis +4
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM
paper · pdf · doi:10.48550/arxiv.cs/0607092
12 pages, 0 figures
openalex publication_date 2006/07/19 · arxiv created 2008/03/26 · arxiv updated 2009/12/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
A unit cube in k dimensional space (or k-cube in short) is defined as the Cartesian product R1× R2×...× Rk where Ri(for 1≤ i≤ k) is a closed interval of the form [ai,ai+1] on the real line. A k-cube representation of a graph G is a mapping of the vertices of G to k-cubes such that two vertices in G are adjacent if and only if their corresponding k-cubes have a non-empty intersection. The cubicity of G, denoted as \cubi(G), is the minimum k such that G has a k-cube representation. Roberts \citeRoberts showed that for any graph G on n vertices, \cubi(G)≤ 2n/3. Many NP-complete graph problems have polynomial time deterministic algorithms or have good approximation ratios in graphs of low cubicity. In most of these algorithms, computing a low dimensional cube representation of the given graph is usually the first step. We present an efficient algorithm to compute the k-cube representation of G with maximum degree Δ in O(Δln b) dimensions where b is the bandwidth of G. Bandwidth of G is at most n and can be much lower. The algorithm takes as input a bandwidth ordering of the vertices in G. Though computing the bandwidth ordering of vertices for a graph is NP-hard, there are heuristics that perform very well in practice. Even theoretically, there is an O(log4 n) approximation algorithm for computing the bandwidth ordering of a graph using which our algorithm can produce a k-cube representation of any given graph in k=O(Δ(ln b + lnln n)) dimensions. Both the bounds on cubicity are shown to be tight upto a factor of O(loglog n).