Finding a Box Representation for a Graph in O(n2Δ2lnn) Time
L. Sunil Chandran, Mathew C. Francis, Rogers Mathew · 2008
An axis-parallel box in b-dimensional space is a Cartesian product R1×R2×...×Rbwhere Ri(for 1 ≤ i ≤ b) is a closed interval of the form [ai, bi] on the real line. For a graph G, its boxicity is the minimum dimension b, such that G is representable as the intersection graph of (axis-parallel) boxes in b-dimensional space. The concept of boxicity finds application in various areas of research like ecology, operation research etc. Chandran, Francis and Sivadasan gave an O(Δn2ln2n) randomized algorithm to construct a box representation for any graph G on n vertices in [(Δ+2)lnn] dimensions, where Δ is the maximum degree of the graph. They also came up with a deterministic algorithm that runs in O(n4Δ) time. Here, we present an O(n2Δ2lnn) deterministic algorithm that constructs the box representation for any graph in [(Δ+2)lnn] dimensions.