Boxicity and treewidth

DOI10.1016/J.JCTB.2006.12.004MaRDI QIDQ2642011zbMATH OpenOpenAlexFDO

Authors L. Sunil Chandran, Naveen Sivadasan

Publication date 20 August 2007

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0505544

treewidth intersection graphs graph classes boxicity

Graph representations (geometric and intersection representations, etc.) (05C62) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: 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.

Recommendations

Cites work

Cited in

(42)

This page was built for publication: Boxicity and treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2642011)