Boxicity and treewidth
From MaRDI portal
Publication:2642011
DOI10.1016/J.JCTB.2006.12.004zbMATH Open1121.05091arXivmath/0505544OpenAlexW2034198559MaRDI QIDQ2642011FDOQ2642011
Authors: L. Sunil Chandran, Naveen Sivadasan 
Publication date: 20 August 2007
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/math/0505544
Recommendations
- Treewidth: Characterizations, Applications, and Computations
- scientific article; zbMATH DE number 1361465
- Treewidth: Structure and Algorithms
- Boolean dimension and tree-width
- On treewidth approximations
- scientific article; zbMATH DE number 1944139
- Treewidth computations. I: Upper bounds
- Treewidth of grid subsets
- Tree-width in algebraic complexity
Graph representations (geometric and intersection representations, etc.) (05C62) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- Graph Classes: A Survey
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Treewidth for graphs with small chordality
- Graph minors. XIII: The disjoint paths problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- The Complexity of the Partial Order Dimension Problem
- Interval representations of planar graphs
- A special planar satisfiability problem and a consequence of its NP- completeness
- Boxicity and treewidth
- Title not available (Why is that?)
- Parallel Algorithms with Optimal Speedup for Bounded Treewidth
- Optimal packing and covering in the plane are NP-complete
- Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
- Title not available (Why is that?)
- Tree-width and circumference of graphs
- Grid intersection graphs and boxicity
- Approximating the Bandwidth for Asteroidal Triple-Free Graphs
- Computing the boxicity of a graph by covering its complement by cointerval graphs
- A note on circular dimension
- The circular dimension of a graph
- Poset boxicity of graphs
Cited In (39)
- Product dimension of forests and bounded treewidth graphs
- Boxicity of Halin graphs
- A note on lower bounds for boxicity of graphs
- Treewidth computations. II. Lower bounds
- Boxicity of leaf powers
- Boxicity of circular arc graphs
- Chordal bipartite graphs with high boxicity
- Sublinear approximation algorithms for boxicity and related problems
- Orthogonal tree decompositions of graphs
- Geometric representation of graphs in low dimension using axis parallel boxes
- Dimension-2 poset competition numbers and dimension-2 poset double competition numbers
- Boxicity and cubicity of asteroidal triple free graphs
- Boxicity of graphs with bounded degree
- The cubicity of hypercube graphs
- Bounds for the boxicity of Mycielski graphs
- Bounding threshold dimension: realizing graphic Boolean functions as the AND of majority gates
- Cubicity, degeneracy, and crossing number
- Structural parameterizations for boxicity
- A note on the intersection property for flat boxes and boxicity in \(\mathbb R^d\)
- Separation dimension of graphs and hypergraphs
- Boxicity of line graphs
- On Comparable Box Dimension
- On the Cubicity of Interval Graphs
- Lower bounds for boxicity
- Intersection dimension and graph invariants
- On the stab number of rectangle intersection graphs
- An upper bound for cubicity in terms of boxicity
- Boxicity and maximum degree
- Geometric Representation of Graphs in Low Dimension
- Representing graphs as the intersection of cographs and threshold graphs
- On the cubicity of interval graphs
- On the boxicity of Kneser graphs and complements of line graphs
- Boxicity of graphs on surfaces
- Boxicity and topological invariants
- Cubicity, boxicity, and vertex cover
- Boxicity and treewidth
- Better bounds for poset dimension and boxicity
- Chronological rectangle digraphs which are two-terminal series-parallel
- A constant factor approximation algorithm for boxicity of circular arc graphs
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)
