# zbMATH — the first resource for mathematics

Boxicity and treewidth. (English) Zbl 1121.05091
Summary: An axis-parallel $$b$$-dimensional box is a Cartesian product $$R_{1} \times R_{2} \times \cdots \times R_{b}$$ where $$R_{i}$$ (for 1 $$\leqslant i \leqslant b$$) is a closed interval of the form $$[a_{i},b_{i}]$$ on the real line. For a graph $$G$$, its boxicity box($$G$$) is the minimum dimension $$b$$ such that $$G$$ is representable as the intersection graph of (axis-parallel) boxes in $$b$$-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operation research, etc. Though many authors have investigated this concept, not much is known about the boxicity of many well-known graph classes (except for a couple of cases) perhaps due to lack of effective approaches. Also, little is known about the structure imposed on a graph by its high boxicity.
The concepts of tree decomposition and treewidth play a very important role in modern graph theory and have many applications to computer science. In this paper, we relate the seemingly unrelated concepts of treewidth and boxicity. Our main result is that, for any graph $$G$$, box$$(G) \leqslant \text{tw}(G)+2$$, where box($$G$$) and tw$$(G)$$ denote the boxicity and treewidth of $$G$$, respectively. We also show that this upper bound is (almost) tight. Since treewidth and tree decompositions are extensively studied concepts, 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. For all these graph classes, no bounds on their boxicity were known previously. 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 constant dimensional space.

##### MSC:
 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C62 Graph representations (geometric and intersection representations, etc.)
##### Keywords:
intersection graphs; treewidth; boxicity; graph classes
Full Text:
##### References:
  Arnborg, S., Efficient algorithms for combinatorial problems on graphs with bounded decomposability—a survey, Bit, 25, 2-23, (1985) · Zbl 0573.68018  Arnborg, S.; Proskurowski, A., Linear time algorithms for NP-hard problems on graphs embedded in k-trees, Discrete appl. math., 23, 11-24, (1989) · Zbl 0666.68067  Bellantoni, S.; Ben-Arroyo Hartman, I.; Przytycka, T.; Whitesides, S., Grid intersection graphs and boxicity, Discrete math., 114, 1-3, 41-49, (April 1993)  Birmele, E., Tree-width and circumference of graphs, J. graph theory, 43, 1, 24-25, (2003) · Zbl 1017.05036  Bodlaender, H.L., A tourist guide through treewidth, Acta cybernet., 11, 1-21, (1993) · Zbl 0804.68101  Bodlaender, H.L., A linear time algorithm for finding tree decompositions of small treewidth, SIAM J. comput., 25, 1305-1317, (1996) · Zbl 0864.68074  Bodlaender, H.L.; Hagerup, T., Parallel algorithms with optimal speedup for bounded treewidth, SIAM J. comput., 27, 1725-1746, (1998) · Zbl 0907.68089  Bodlaender, H.L.; Thilikos, D.M., Treewidth for graphs with small chordality, Discrete appl. math., 79, 45-61, (1997) · Zbl 0895.68113  Brandstädt, Andreas; Le, V. Bang; Spinrad, Jeremy P., Graph classes: A survey, (1999), SIAM · Zbl 0919.05001  Chandran, L. Sunil; Sivadasan, Naveen, Treewidth and boxicity, (2005), technical report, available at · Zbl 1121.05091  Chang, Y.W.; West, Douglas B., Interval number and boxicity of digraphs, ()  Chang, Y.W.; West, Douglas B., Rectangle number for hyper cubes and complete multipartite graphs, 29th SE conf. comb., graph th. and comp., Congr. numer., 132, 19-28, (1998) · Zbl 0951.05055  M.B. Cozzens, Higher and multidimensional analogues of interval graphs, PhD thesis, Rutgers University, New Brunswick, NJ, 1981  Cozzens, M.B.; Roberts, F.S., Computing the boxicity of a graph by covering its complement by cointerval graphs, Discrete appl. math., 6, 217-228, (1983) · Zbl 0524.05059  Diestel, Reinhard, Graph theory, vol. 173, (2000), Springer-Verlag New York · Zbl 0945.05002  Feinberg, Robert B., The circular dimension of a graph, Discrete math., 25, 1, 27-31, (1979) · Zbl 0392.05057  Fowler, R.J.; Paterson, M.S.; Tanimoto, S.L., Optimal packing and covering in the plane are NP-complete, Inform. process. lett., 12, 3, 133-137, (1981) · Zbl 0469.68053  Golumbic, Martin C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054  Imai, H.; Asano, T., Finding the connected component and a maximum clique of an intersection graph of rectangles in the plane, J. algorithms, 4, 310-323, (1983) · Zbl 0548.68067  Kloks, T.; Kratsch, D.; Müller, H., Approximating the bandwidth of asteroidal triple-free graphs, J. algorithms, 32, 1, 41-57, (1999) · Zbl 0951.68113  Kratochvil, J., A special planar satisfiability problem and a consequence of its NP-completeness, Discrete appl. math., 52, 233-252, (1994) · Zbl 0810.68083  Roberts, F.S., On the boxicity and cubicity of a graph, (), 301-310 · Zbl 0193.24301  Robertson, N.; Seymour, P.D., Graph minors XIII. the disjoint paths problem, J. combin. theory ser. B, 63, 65-110, (1995) · Zbl 0823.05038  E.R. Scheinerman, Intersection classes and multiple intersection parameters, PhD thesis, Princeton University, 1984  Shearer, J.B., A note on circular dimension, Discrete math., 29, 1, 103, (1980) · Zbl 0437.05049  Thomassen, C., Interval representations of planar graphs, J. combin. theory ser. B, 40, 9-20, (1986) · Zbl 0595.05027  Trotter, W.T.; West, Douglas B., Poset boxicity of graphs, Discrete math., 64, 1, 105-107, (March 1987)  Yannakakis, Mihalis, The complexity of the partial order dimension problem, SIAM J. algebraic discrete methods, 3, 351-358, (1982) · Zbl 0516.06001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.