Boxicity and Maximum degree

Details Boxicity and Maximum degree Boxicity and Maximum degree

2006-10-08

arxiv.org/abs/math/0610262v1

Mathematics

Combinatorics

4 pages

Scientific paper

An axis-parallel $d$--dimensional box is a Cartesian product $R_1 \times R_2 \times ... \times R_d$ where $R_i$ (for $1 \le i \le d$) is a closed interval of the form $[a_i, b_i]$ on the real line. For a graph $G$, its \emph{boxicity} $\boxi(G)$ is the minimum dimension $d$, such that $G$ is representable as the intersection graph of (axis--parallel) boxes in $d$--dimensional space. The concept of boxicity finds applications in various areas such as ecology, operation research etc. We show that for any graph $G$ with maximum degree $\Delta$, $\boxi(G) \le 2 \Delta^2 + 2$. That the bound does not depend on the number of vertices is a bit surprising considering the fact that there are highly connected bounded degree graphs such as expander graphs. Our proof is very short and constructive. We conjecture that $\boxi(G)$ is $O(\Delta)$.

Affiliated with

Also associated with

No associations

Rating

Boxicity and Maximum degree does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Boxicity and Maximum degree, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Boxicity and Maximum degree will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-518724