Chandran, L S and Francis, M C and Sivadasan, N
(2013)
Cubicity and Bandwidth.
Graphs and Combinatorics, 29 (1).
pp. 4569.
ISSN 09110119
Full text not available from this repository.
(
Request a copy)
Abstract
A unit cube in ℝk (or a kcube 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 kcube representation of a graph G is a mapping of the vertices of G to kcubes such that two vertices in G are adjacent if and only if their corresponding kcubes have a nonempty intersection. The cubicity of G is the minimum k such that G has a kcube representation. From a geometric embedding point of view, a kcube representation of G = (V, E) yields an embedding f: V(G) → ℝk such that for any two vertices u and v, {double pipe}f(u)  f(v){double pipe}∞ ≤ 1 if and only if (u, v) ∈ E(G). We first present a randomized algorithm that constructs the cube representation of any graph on n vertices with maximum degree Δ in O(Δ ln n) dimensions. This algorithm is then derandomized to obtain a polynomial time deterministic algorithm that also produces the cube representation of the input graph in the same number of dimensions. The bandwidth ordering of the graph is studied next and it is shown that our algorithm can be improved to produce a cube representation of the input graph G in O(Δ ln b) dimensions, where b is the bandwidth of G, given a bandwidth ordering of G. Note that b ≤ n and b is much smaller than n for many wellknown graph classes. Another upper bound of b + 1 on the cubicity of any graph with bandwidth b is also shown. Together, these results imply that for any graph G with maximum degree Δ and bandwidth b, the cubicity is O(min{b, Δ ln b}). The upper bound of b + 1 is used to derive upper bounds for the cubicity of circulararc graphs, cocomparability graphs and ATfree graphs in terms of the maximum degree Δ
[error in script]
Actions (login required)

View Item 