Boxicitás

Téglalapok metszetgráfja, boxicitás = 2

A matematika, azon belül a gráfelmélet területén a boxicitás, boxicity paraméter vagy hipertéglatest-dimenzió egy Fred S. Roberts által 1969-ben bevezetett gráfparaméter. Egy gráf boxicitása az a minimális dimenzió, melyben adott gráf felírható egymással párhuzamos tengelyű hipertéglatestek metszetgráfjaként. Tehát ha a gráf csúcsai és a hipertéglatestek halmaza között kölcsönös megfeleltetés létesíthető oly módon, hogy két hipertéglatest pontosan akkor metszi egymást, ha a nekik megfelelő csúcsok között él húzódik.

Példák

Az ábrán egy hat csúcsú gráf és téglalapok (kétdimenziós hipertéglatestek) metszetgráfjaként való reprezentációja látható. Ez a gráf nem ábrázolható alacsonyabb dimenziójú hipertéglatestek metszetgráfjaként (pl. intervallumgráfként), ezért boxicity paramétere kettő. (Roberts 1969) megmutatta, hogy a 2n csúcsú csúcsú teljes gráfból egy teljes párosítás eltávolításával kapott gráf boxicitása éppen n: minden eltávolított csúcspárt másik dimenzióban elválasztott hipertéglatesteknek kell reprezentálnia, mint a többi párt. Ennek a gráfnak egy konkrét hipertéglatest-reprezentációját elő lehet állítani egy n dimenziós hiperkocka hiperlapjainak hipertéglatestté vastagításával. Az eredmény alapján ezt a gráfot Roberts-gráfnak is hívják, bár ismertebb neve koktélpartigráf, illetve tekinthető úgy is, hogy ez a T(2n,n) Turán-gráf.

Más gráfcsaládokkal való kapcsolata

Egy gráf boxicity paramétere pontosan akkor egy, ha intervallumgráf (az intervallum felfogható egydimenziós téglatestként). A külsíkgráfok boxicitása legfeljebb kettő, az általánosabb síkbarajzolható gráfoké pedig legfeljebb három. Ha egy páros gráf boxicitása kettő, előállítható egy síkbeli derékszögű koordináta-rendszer tengelyeivel párhuzamos intervallumok metszetgráfjaként.

Algoritmikus eredmények

Számos gráfokkal kapcsolatos probléma az általános esetnél egyszerűbben megoldható korlátozott boxicitású gráfokra. Például a maximálisklikk-probléma korlátos boxicitású gráfokra polinom időben megoldható. Néhány más gráfproblémánál a hatékony megoldást vagy a jó közelítő megoldást elősegíti, ha ismert a gráf egy alacsony dimenziószámú hipertéglatest-reprezentációja. Az ilyen reprezentáció előállítása azonban nehéz: NP-teljes annak tesztelése, hogy adott gráf boxicitása K-val egyezik-e, még K = 2-re is.

A (Chandran, Francis & Sivadasan 2010) leír néhány algoritmust tetszőleges gráfok hipertéglatest-metszetgráfként való reprezentációinak előállítására, a gráf maximális fokszámával logaritmikus faktor közelségben lévő dimenziószámmal; ez az eredmény egyben megad egy felső korlátot a gráf boxicitására.

Bár a boxicitás meghatározása nehéz probléma, a bemeneti gráf csúcslefedési számával parametrizálva rögzített paraméter mellett kezelhető.

Korlátok

Louis Esperet a G gráf boxicitására a gráf élszámának, m-nek függvényében a következő, aszimptotikusan optimális korlátot igazolta:

$\operatorname {box} (G)=O\left({\sqrt {m\cdot \log(m)}}\right)$.

Kapcsolódó gráfparaméterek

• Cubicity: hipertéglatestek helyett egységnyi (hiper)kockák szerepelnek; a boxicity a cubicity általánosítása
• Sphericity: hipertéglatestek helyett egységnyi (hiper)gömbök szerepelnek

Ugyanazon gráf Colin de Verdière-invariánsa és boxicitása között Louis Esperet a következő összefüggést igazolta:

$\operatorname {box} (G)=O\left(\mu (G)^{4}(\log(\mu (G))^{2}\right)$,

továbbá valószínűsíti, hogy a boxicitás legfeljebb a Colin de Verdière-invariánssal egyenlő.

Fordítás

• Ez a szócikk részben vagy egészben a Boxicity című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

• Adiga, Abhijin; Chitnis, Rajesh & Saurabh, Saket (2010), "Parameterized algorithms for boxicity", Algorithms and Computation: 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I, vol. 6506, Lecture Notes in Computer Science, pp. 366–377, doi:10.1007/978-3-642-17517-6_33, <http://www.wisdom.weizmann.ac.il/~chitnis/fptBoxicity.pdf>. Hozzáférés ideje: 2018-01-22 Archiválva 2017. augusztus 30-i dátummal a Wayback Machine-ben
• Agarwal, Pankaj K.; van Kreveld, Marc & Suri, Subhash (1998), "Label placement by maximum independent set in rectangles", Computational Geometry Theory and Applications 11 (3–4): 209–218, DOI 10.1016/S0925-7721(98)00028-5.
• Bellantoni, Stephen J.; Ben-Arroyo Hartman, Irith & Przytycka, Teresa et al. (1993), "Grid intersection graphs and boxicity", Discrete Mathematics 114 (1–3): 41–49, DOI 10.1016/0012-365X(93)90354-V.
• Berman, Piotr; DasGupta, B. & Muthukrishnan, S. et al. (2001), "Efficient approximation algorithms for tiling and packing problems with rectangles", J. Algorithms 41 (2): 443–470, DOI 10.1006/jagm.2001.1188.
• Chandran, L. Sunil; Francis, Mathew C. & Sivadasan, Naveen (2010), "Geometric representation of graphs in low dimension using axis parallel boxes", Algorithmica 56 (2): 129–140, DOI 10.1007/s00453-008-9163-5.
• Chandran, L. Sunil & Sivadasan, Naveen (2007), "Boxicity and treewidth", Journal of Combinatorial Theory, Series B 97 (5): 733–744, DOI 10.1016/j.jctb.2006.12.004.
• Chlebík, Miroslav & Chlebíková, Janka (2005), "Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes", Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 267–276, <http://portal.acm.org/citation.cfm?id=1070470>.
• Cozzens, M. B. (1981), Higher and Multidimensional Analogues of Interval Graphs, Ph.D. thesis, Rutgers University.
• Kratochvil, Jan (1994), "A special planar satisfiability problem and a consequence of its NP–completeness", Discrete Applied Mathematics 52 (3): 233–252, DOI 10.1016/0166-218X(94)90143-0.
• Quest, M. & Wegner, G. (1990), "Characterization of the graphs with boxicity ≤ 2", Discrete Mathematics 81 (2): 187–192, DOI 10.1016/0012-365X(90)90151-7.
• Roberts, F. S. (1969), "On the boxicity and cubicity of a graph", in Tutte, W. T., Recent Progress in Combinatorics, Academic Press, pp. 301–310, ISBN 978-0-12-705150-5.
• Scheinerman, E. R. (1984), Intersection Classes and Multiple Intersection Parameters, Ph. D thesis, Princeton University.
• Thomassen, Carsten (1986), "Interval representations of planar graphs", Journal of Combinatorial Theory, Series B 40: 9–20, DOI 10.1016/0095-8956(86)90061-4.
• Yannakakis, Mihalis (1982), "The complexity of the partial order dimension problem", SIAM Journal on Algebraic and Discrete Methods 3 (3): 351–358, DOI 10.1137/0603036.
• Bhowmick, Diptendu; Chandran, L. Sunil & Adiga, Abhijin (2011), "Boxicity and Poset Dimension", SIAM Journal on Discrete Mathematics 25 (4): 1687–1698, DOI 10.1137/100786290.