请输入您要查询的百科知识：

　

词条 Boxicity
释义

  1. Examples

  2. Relation to other graph classes

  3. Algorithmic results

  4. Bounds

  5. Related graph invariants

  6. Notes

  7. References

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 2n vertices formed by removing a perfect matching from a complete graph on 2n 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 2n facets of an n-dimensional hypercube into a box. Because of these results, this graph has been called the Roberts graph,[1] although it is better known as the cocktail party graph and it can also be understood as the Turán graph T(2n,n).

Relation to other graph classes

A graph has boxicity at most one if and only if it is an interval graph; the boxicity of an arbitrary graph G is the minimum number of interval graphs on the same set of vertices such that the intersection of the edges sets of the interval graphs is G. Every outerplanar graph has boxicity at most two,[2] and every planar graph has boxicity at most three.[3]

If a bipartite graph has boxicity two, it can be represented as an intersection graph of axis-parallel line segments in the plane.[4]

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.[5] For some other graph problems, an efficient solution or approximation can be found if a low-dimensional box representation is known.[6] 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.[7]

{{harvtxt|Chandran|Francis|Sivadasan|2010}} 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.

Despite being hard for its natural parameter, boxicity is fixed-parameter tractable when parameterized by the vertex cover number of the input graph.[8]

Bounds

Louis Esperet proved the following bound of the boxicity of G graph with m edges, which is asymptotically optimal:
.[9]

Related graph invariants

  • Cubicity is defined in the same way as boxicity but with axis-parallel hypercubes instead of hyperrectangles. Boxicity is a generalization of cubicity.
  • Sphericity is defined in the same way as boxicity but with unit-diameter spheres.

Louis Esperet proved the following connection between the Colin de Verdière invariant and boxicity of the same graph:

, and conjectured that the boxicity of G is at most the Colin de Verdière invariant of G.[9]

Notes

1. ^E.g., see {{harvtxt|Chandran|Francis|Sivadasan|2010}} and {{harvtxt|Chandran|Sivadasan|2007}}.
2. ^{{harvtxt|Scheinerman|1984}}.
3. ^{{harvtxt|Thomassen|1986}}.
4. ^{{harvtxt|Bellantoni|Ben-Arroyo Hartman|Przytycka|Whitesides|1993}}.
5. ^{{harvtxt|Chandran|Francis|Sivadasan|2010}} observe that this follows from the fact that these graphs have a polynomial number of maximal cliques. An explicit box representation is not needed to list all maximal cliques efficiently.
6. ^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.
7. ^{{harvtxt|Cozzens|1981}} shows that computing the boxicity is NP-complete; {{harvtxt|Yannakakis|1982}} shows that even checking whether the boxicity is at most 3 is NP-hard; finally {{harvtxt|Kratochvil|1994}} showed that recognising boxicity 2 is NP-hard.
8. ^{{harvtxt|Adiga|Chitnis|Saurabh|2010}}.
9. ^1 {{cite arXiv |last=Esperet |first=Louis |date=2015 |title=Boxicity and Topological Invariants|eprint=1503.05765 |class=math.CO}}

References

{{refbegin|30em}}
  • {{citation

| last1 = Adiga
| first1 = Abhijin
| last2 = Chitnis
| first2 = Rajesh
| last3 = Saurabh
| first3 = Saket
| contribution = Parameterized algorithms for boxicity
| doi = 10.1007/978-3-642-17517-6_33
| pages = 366–377
| series = Lecture Notes in Computer Science
| title = Algorithms and Computation: 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I
| url = http://www.wisdom.weizmann.ac.il/~chitnis/fptBoxicity.pdf
| volume = 6506
| year = 2010
  • {{citation

| first1 = Pankaj K. | last1 = Agarwal | author1-link = Pankaj K. Agarwal
| first2 = Marc | last2 = van Kreveld
| first3 = Subhash | last3 = Suri | author3-link = Subhash 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
| issue = 3–4}}.
  • {{citation

| last1 = Bellantoni | first1 = Stephen J.
| last2 = Ben-Arroyo Hartman | first2 = Irith
| last3 = Przytycka | first3 = Teresa
| last4 = Whitesides | first4 = Sue | author4-link = Sue Whitesides
| 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
| issue = 2}}.
  • {{citation

| last1 = Chandran | first1 = L. Sunil
| last2 = Francis | first2 = Mathew C.
| last3 = Sivadasan | first3 = Naveen
| arxiv = cs.DM/0605013
| doi = 10.1007/s00453-008-9163-5
| issue = 2
| journal = Algorithmica
| mr = 2576537
| pages = 129–140
| title = Geometric representation of graphs in low dimension using axis parallel boxes
| volume = 56
| year = 2010}}.
  • {{citation

| last1 = Chandran | first1 = L. Sunil
| last2 = Sivadasan | first2 = Naveen
| title = Boxicity and treewidth
| journal = Journal of Combinatorial Theory | series = Series B
| volume = 97 | issue = 5 | year = 2007 | pages = 733–744 | doi = 10.1016/j.jctb.2006.12.004
| 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 | authorlink = Jan Kratochvíl
| 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
| issue = 3}}.
  • {{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. | authorlink = Fred S. Roberts
| 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-0-12-705150-5
| year = 1969 | pages = 301–310}}.
  • {{citation

| first = E. R. | last = Scheinerman | authorlink = Ed 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
| authorlink = Mihalis Yannakakis
| title = The complexity of the partial order dimension problem
| journal = SIAM Journal on Algebraic and Discrete Methods
| volume = 3 | year = 1982 | pages = 351–358 | doi = 10.1137/0603036
| issue = 3}}.
  • {{citation

| first1 = Diptendu | last1 = Bhowmick
| last2 = Chandran | first2 = L. Sunil
| first3 = Abhijin | last3 = Adiga
| title = Boxicity and Poset Dimension
| journal = SIAM Journal on Discrete Mathematics
| volume = 25 | year = 2011 | pages = 1687–1698 | doi = 10.1137/100786290
| issue = 4| arxiv = 1003.2357}}.{{refend}}

2 : Geometric graph theory|Graph invariants
随便看

　

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

　

Copyright © 2023 OENC.NET All Rights Reserved
京ICP备2021023879号 更新时间：2024/11/11 1:42:02