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.)
Full Text:
References:
 [1] Arnborg, S., Efficient algorithms for combinatorial problems on graphs with bounded decomposability—a survey, Bit, 25, 2-23, (1985) · Zbl 0573.68018 [2] 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 [3] Bellantoni, S.; Ben-Arroyo Hartman, I.; Przytycka, T.; Whitesides, S., Grid intersection graphs and boxicity, Discrete math., 114, 1-3, 41-49, (April 1993) [4] Birmele, E., Tree-width and circumference of graphs, J. graph theory, 43, 1, 24-25, (2003) · Zbl 1017.05036 [5] Bodlaender, H.L., A tourist guide through treewidth, Acta cybernet., 11, 1-21, (1993) · Zbl 0804.68101 [6] Bodlaender, H.L., A linear time algorithm for finding tree decompositions of small treewidth, SIAM J. comput., 25, 1305-1317, (1996) · Zbl 0864.68074 [7] Bodlaender, H.L.; Hagerup, T., Parallel algorithms with optimal speedup for bounded treewidth, SIAM J. comput., 27, 1725-1746, (1998) · Zbl 0907.68089 [8] Bodlaender, H.L.; Thilikos, D.M., Treewidth for graphs with small chordality, Discrete appl. math., 79, 45-61, (1997) · Zbl 0895.68113 [9] Brandstädt, Andreas; Le, V. Bang; Spinrad, Jeremy P., Graph classes: A survey, (1999), SIAM · Zbl 0919.05001 [10] Chandran, L. Sunil; Sivadasan, Naveen, Treewidth and boxicity, (2005), technical report, available at · Zbl 1121.05091 [11] Chang, Y.W.; West, Douglas B., Interval number and boxicity of digraphs, () [12] 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 [13] M.B. Cozzens, Higher and multidimensional analogues of interval graphs, PhD thesis, Rutgers University, New Brunswick, NJ, 1981 [14] 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 [15] Diestel, Reinhard, Graph theory, vol. 173, (2000), Springer-Verlag New York · Zbl 0945.05002 [16] Feinberg, Robert B., The circular dimension of a graph, Discrete math., 25, 1, 27-31, (1979) · Zbl 0392.05057 [17] 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 [18] Golumbic, Martin C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054 [19] 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 [20] 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 [21] Kratochvil, J., A special planar satisfiability problem and a consequence of its NP-completeness, Discrete appl. math., 52, 233-252, (1994) · Zbl 0810.68083 [22] Roberts, F.S., On the boxicity and cubicity of a graph, (), 301-310 · Zbl 0193.24301 [23] Robertson, N.; Seymour, P.D., Graph minors XIII. the disjoint paths problem, J. combin. theory ser. B, 63, 65-110, (1995) · Zbl 0823.05038 [24] E.R. Scheinerman, Intersection classes and multiple intersection parameters, PhD thesis, Princeton University, 1984 [25] Shearer, J.B., A note on circular dimension, Discrete math., 29, 1, 103, (1980) · Zbl 0437.05049 [26] Thomassen, C., Interval representations of planar graphs, J. combin. theory ser. B, 40, 9-20, (1986) · Zbl 0595.05027 [27] Trotter, W.T.; West, Douglas B., Poset boxicity of graphs, Discrete math., 64, 1, 105-107, (March 1987) [28] 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.