On the Cubicity of AT-Free Graphs and Circular-Arc Graphs

摘要

A unit cube in k dimensions (k-cube) is defined as the Cartesian product R_1 × R_2 ×... × R_k where R_i (for 1 ≤ i ≤ k) is a closed interval of the form [a_i,a_i + 1] on the real line. A graph G on n nodes is said to be representable as the intersection of k-cubes (cube representation in k dimensions) if each vertex of G can be mapped to a k-cube such that two vertices are adjacent in G if and only if their corresponding k-cubes have a non-empty intersection. The cubicity of G denoted as cub(G) is the minimum k for which G can be represented as the intersection of k-cubes.rnAn interesting aspect about cubicity is that many problems known to be NP-complete for general graphs 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.rnWe give an O(bw · n) algorithm to compute the cube representation of a general graph G in bw + 1 dimensions given a bandwidth ordering of the vertices of G, where bw is the bandwidth of G. As a consequence, we get O(△) upper bounds on the cubicity of many well-known graph classes such as AT-free graphs, circular-arc graphs and cocomparability graphs which have O(△) bandwidth. Thus we have:rn1. cub(G) ≤ 3△ - 1, if G is an AT-free graph.rn2. cub(G) ≤ 2△ + 1, if G is a circular-arc graph.rn3. cub(G) ≤ 2△, if G is a cocomparability graph.rnAlso for these graph classes, there are constant factor approximation algorithms for bandwidth computation that generate orderings of vertices with O(△) width. We can thus generate the cube representation of such graphs in O(△) dimensions in polynomial time.