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.

An 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.

We 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:

1

cub(

G

) ≤ 3Δ− 1, if

G

is an AT-free graph.

1

cub(

G

) ≤ 2Δ + 1, if

G

is a circular-arc graph.

1

cub(

G

) ≤ 2Δ, if

G

is a cocomparability graph.

Also 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.