Boxicity and Treewidth

Details Boxicity and Treewidth Boxicity and Treewidth

2005-05-25

arxiv.org/abs/math/0505544v1

Mathematics

Combinatorics

25 pages

Scientific paper

In this paper, we relate the seemingly unrelated concepts of treewidth and boxicity. Our main result is that, for any graph G, boxicity(G) <= treewidth(G) + 2. We also show that this upper bound is (almost) tight. Our result leads to various interesting consequences, like bounding the boxicity of many well known graph classes, such as chordal graphs, circular arc graphs, AT-free graphs, co--comparability graphs etc. All our bounds are shown to be tight up to small constant factors. An algorithmic consequence of our result is a linear time algorithm to construct a box representation for graphs of bounded treewidth in a space of constant dimension. We also show many structural results as a consequence. In particular, we show that, if the boxicity of a graph is b >= 3, then there exists a simple cycle of length at least b-3 as well as an induced cycle of length at least floor of (log(b-2) to the base Delta) + 2, where Delta is its maximum degree. We also relate boxicity with the cardinality of minimum vertex cover, minimum feedback vertex cover etc. Another structural consequence is that, for any fixed planar graph H, there is a constant c(H) such that, if boxicity(G) >= c(H) then H is a minor of G.

Affiliated with

Also associated with

No associations

Rating

Boxicity and Treewidth 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 Treewidth, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Boxicity and Treewidth will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-642010