
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.
25 pages
Intersection graphs, boxicity, Treewidth, Graph classes, graph classes, Graph representations (geometric and intersection representations, etc.), 511, School of Automation), intersection graphs, Theoretical Computer Science, Computational Theory and Mathematics, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), Computer Science & Automation (Formerly, treewidth, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Combinatorics (math.CO), 05C62, Boxicity
Intersection graphs, boxicity, Treewidth, Graph classes, graph classes, Graph representations (geometric and intersection representations, etc.), 511, School of Automation), intersection graphs, Theoretical Computer Science, Computational Theory and Mathematics, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), Computer Science & Automation (Formerly, treewidth, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Combinatorics (math.CO), 05C62, Boxicity
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 42 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
