Boxicity

In graph theory, boxicity is a graph invariant, introduced by Fred S. Roberts in 1969.

The boxicity of a graph is the minimum dimension in which a given graph can be represented as an intersection graph of axis parallel boxes. That is, there must exist a one-to-one correspondence between the vertices of the graph and a set of boxes, such that two boxes intersect if and only if there is an edge connecting the corresponding vertices.

Examples

The figure shows a graph with six vertices, and a representation of this graph as an intersection graph of rectangles (two-dimensional boxes). This graph cannot be represented as an intersection graph of boxes in any lower dimension, so its boxicity is two.

harvtxt|Roberts|1969 showed that the graph with 2"n" vertices, formed by removing a perfect matching from a complete graph on 2"n" vertices, has boxicity exactly "n": each pair of disconnected vertices must be represented by boxes that are separated in a different dimension than each other pair. A box representation of this graph with dimension exactly "n" can be found by thickening each of the 2"n" facets of an "n"-dimensional hypercube into a box. Because of these results, this graph has been called the "Roberts graph", [E.g., see harvtxt|Chandran|Francis|Sivadasan|2006 and harvtxt|Chandran|Sivadasan|2007.] although it can also be understood as the Turán graph "T"(2"n","n").

Relation to other graph classes

A graph has boxicity at most one if and only if it is an interval graph. Every outerplanar graph has boxicity at most two, [harvtxt|Scheinerman|1984.] and every planar graph has boxicity at most three. [harvtxt|Thomassen|1986.]

If a bipartite graph has boxicity two, it can be represented as an intersection graph of axis-parallel line segments in the plane. [harvtxt|Bellantoni|Ben-Arroyo Hartman|Przytycka|Whitesides|1993.]

Algorithmic results

Many graph problems can be solved or approximated more efficiently for graphs with bounded boxicity than they can for other graphs; for instance, the maximum clique problem can be solved in polynomial time for graphs with bounded boxicity. [harvtxt|Chandran|Francis|Sivadasan|2006 observe that this follows from the fact that these graphs have a polynomial number of maximal cliques. An explicit box representatation is not needed to list all maximal cliques efficiently.] For some other graph problems, an efficient solution or approximation can be found if a low-dimensional box representation is known. [See, e.g., harvtxt|Agarwal|van Kreveld|Suri|1998 and harvtxt|Berman|DasGupta|Muthukrishnan|Ramaswami|2001 for approximations to the maximum independent set for intersection graphs of rectangles, and harvtxt|Chlebík|Chlebíková|2005 for results on hardness of approximation of these problems in higher dimensions.] However, finding such a representation may be difficult:it is NP-complete to test whether the boxicity of a given graph is at most some given value "K", even for "K" = 2. [harvtxt|Cozzens|1981; harvtxt|Yannakakis|1982; harvtxt|Kratochvil|1994.] harvtxt|Chandran|Francis|Sivadasan|2006 describe algorithms for finding representations of arbitrary graphs as intersection graphs of boxes, with a dimension that is within a logarithmic factor of the maximum degree of the graph; this result provides an upper bound on the graph's boxicity.

Notes

References

*citation
first1 = Pankaj K. | last1 = Agarwal
first2 = Marc | last2 = van Kreveld
first3 = Subhash | last3 = Suri
title = Label placement by maximum independent set in rectangles
journal = Computational Geometry Theory and Applications
volume = 11 | year = 1998 | pages = 209–218 | doi = 10.1016/S0925-7721(98)00028-5.

*citation
last1 = Bellantoni | first1 = Stephen J.
last2 = Ben-Arroyo Hartman | first2 = Irith
last3 = Przytycka | first3 = Teresa
last4 = Whitesides | first4 = Sue
title = Grid intersection graphs and boxicity
journal = Discrete Mathematics
volume = 114 | issue = 1-3 | pages = 41–49 | year = 1993 | doi = 10.1016/0012-365X(93)90354-V.

*citation
first1 = Piotr | last1 = Berman
first2 = B. | last2 = DasGupta
first3 = S. | last3 = Muthukrishnan
first4 = S. | last4 = Ramaswami
title = Efficient approximation algorithms for tiling and packing problems with rectangles
journal = J. Algorithms
volume = 41 | year = 2001 | pages = 443–470 | doi = 10.1006/jagm.2001.1188.

*citation
last1 = Chandran | first1 = L. Sunil
last2=Francis | first2=Mathew C.
last3=Sivadasan | first3=Naveen
title = Geometric representation of graphs in low dimension
id=arxiv|cs.DM|0605013
year=2006.

*citation
last1 = Chandran | first1 = L. Sunil
last2 = Sivadasan | first2 = Naveen
title = Boxicity and treewidth
journal = Journal of Combinatorial Theory, Series B
volume = 97 | issue = 5 | year = 2007 | pages = 733–744 | doi = 10.1016/j.jctb.2006.12.004
id = arxiv | math.CO | 0505544.

*citation
first1 = Miroslav | last1 = Chlebík
first2 = Janka | last2 = Chlebíková
contribution = Approximation hardness of optimization problems in intersection graphs of "d"-dimensional boxes
title = Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
year = 2005 | pages = 267–276 | url = http://portal.acm.org/citation.cfm?id=1070470.

*citation
first = M. B. | last = Cozzens
title = Higher and Multidimensional Analogues of Interval Graphs
publisher = Rutgers University
series = Ph.D. thesis
year = 1981.

*citation
first = Jan | last = Kratochvil
title = A special planar satisfiability problem and a consequence of its NP–completeness
journal = Discrete Applied Mathematics
volume = 52 | year = 1994 | pages = 233–252 | doi = 10.1016/0166-218X(94)90143-0.

*citation
last1 = Quest | first1 = M.
last2 = Wegner | first2 = G.
title = Characterization of the graphs with boxicity ≤ 2
journal = Discrete Mathematics
volume = 81 | issue = 2 | year = 1990 | pages = 187–192 | doi = 10.1016/0012-365X(90)90151-7.

*citation
last = Roberts | first = F. S.
contribution = On the boxicity and cubicity of a graph
title = Recent Progress in Combinatorics
editor-first = W. T. | editor-last = Tutte | editor-link = W. T. Tutte
publisher = Academic Press | isbn = 978-0127051505
year = 1969 | pages = 301–310.

*citation
first = E. R. | last = Scheinerman
title = Intersection Classes and Multiple Intersection Parameters
series = Ph. D thesis
publisher = Princeton University
year = 1984.

*citation
first = Carsten | last = Thomassen | authorlink = Carsten Thomassen
title = Interval representations of planar graphs
journal = Journal of Combinatorial Theory, Series B
volume = 40 | year = 1986 | pages = 9–20 | doi = 10.1016/0095-8956(86)90061-4.

*citation
first = Mihalis | last = Yannakakis
title = The complexity of the partial order dimension problem
journal = SIAM Journal on Algebraic Discrete Methods
volume = 3 | year = 1982 | pages = 351–358 | doi = 10.1137/0603036.