- Boxicity
In

graph theory ,**boxicity**is agraph invariant , introduced byFred S. Roberts in 1969.The boxicity of a graph is the minimum

dimension in which a given graph can be represented as anintersection 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 acomplete 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"-dimensionalhypercube 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 theTurá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 . Everyouterplanar graph has boxicity at most two, [*harvtxt|Scheinerman|1984.*] and everyplanar 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*] For some other graph problems, an efficient solution or approximation can be found if a low-dimensional box representation is known. [maximal clique s. An explicit box representatation is not needed to list all maximal cliques efficiently.*See, e.g., harvtxt|Agarwal|van Kreveld|Suri|1998 and harvtxt|Berman|DasGupta|Muthukrishnan|Ramaswami|2001 for approximations to the*] However, finding such a representation may be difficult:it ismaximum 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.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 alogarithm ic 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.

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Turán graph**— The Turán graph T(13,4) Named after Pál Turán v · … Wikipedia**Clique problem**— The brute force algorithm finds a 4 clique in this 7 vertex graph (the complement of the 7 vertex path graph) by systematically checking all C(7,4)=35 4 vertex subgraphs for completeness. In computer science, the clique problem refers to any of… … Wikipedia**List of mathematics articles (B)**— NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… … Wikipedia**Intersection graph**— In the mathematical area of graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph may be represented as an intersection graph, but some important special classes of graphs may… … Wikipedia**Outerplanar graph**— A maximal outerplanar graph and its 3 coloring. In graph theory, an undirected graph is an outerplanar graph if it can be drawn in the plane without crossings in such a way that all of the vertices belong to the unbounded face of the drawing.… … Wikipedia**Graphe planaire extérieur**— Un graphe planaire extérieur maximal, muni d un 3 coloriage. En mathématiques, et plus particulièrement en théorie des graphes, un graphe non orienté est planaire extérieur (ou, par calque de l anglais, outer planar) s il peut être dessiné dans… … Wikipédia en Français