बॉक्सिसिटी

आयतों का प्रतिच्छेदन ग्राफ, बॉक्सिकता दो के साथ

ग्राफ थ्योरी में, बॉक्सिकिटी एक ग्राफ अपरिवर्तनीय है, जिसे 1969 में फ्रेड एस रॉबर्ट्स द्वारा पेश किया गया था।

किसी ग्राफ़ की बॉक्सिकिटी वह न्यूनतम आयाम है जिसमें किसी दिए गए ग्राफ़ को अक्ष-समानांतर बॉक्स (आकार)आकृति) के प्रतिच्छेदन ग्राफ़ के रूप में दर्शाया जा सकता है। अर्थात्, ग्राफ के शीर्ष (ग्राफ सिद्धांत) और बक्सों के एक सेट के बीच एक-से-एक पत्राचार मौजूद होना चाहिए, जैसे कि दो बक्से प्रतिच्छेद करते हैं यदि और केवल अगर संबंधित कोने को जोड़ने वाला किनारा है।

उदाहरण

यह आंकड़ा छह कोने के साथ एक ग्राफ दिखाता है, और आयतों (दो-आयामी बक्से) के एक प्रतिच्छेदन ग्राफ के रूप में इस ग्राफ का प्रतिनिधित्व करता है। इस ग्राफ को किसी भी निचले आयाम में बक्से के प्रतिच्छेदन ग्राफ के रूप में प्रदर्शित नहीं किया जा सकता है, इसलिए इसकी बॉक्सिकता दो है।

Roberts (1969) ने दिखाया कि 2n सिरों पर एक पूर्ण ग्राफ़ से एक पूर्ण मिलान को हटाकर 2n कोने वाले ग्राफ़ में बॉक्सिकता बिल्कुल n है: डिस्कनेक्ट किए गए कोने के प्रत्येक जोड़े को उन बॉक्सों द्वारा दर्शाया जाना चाहिए जो एक दूसरे जोड़े की तुलना में एक अलग आयाम में अलग होते हैं। आयाम के साथ इस ग्राफ का एक बॉक्स प्रतिनिधित्व एन-डायमेंशनल अतिविम के प्रत्येक 2n पहलुओं को एक बॉक्स में मोटा करके पाया जा सकता है। इन परिणामों के कारण, इस ग्राफ को रॉबर्ट्स ग्राफ कहा गया है, हालाँकि इसे कॉकटेल पार्टी ग्राफ के रूप में जाना जाता है और इसे तूरान ग्राफ T(2n,n) के रूप में भी समझा जा सकता है।

अन्य ग्राफ वर्गों से संबंध

एक ग्राफ़ में बॉक्सिकिटी अधिक से अधिक एक होती है यदि और केवल यदि यह एक अंतराल ग्राफ़ है; मनमाना ग्राफ़ G की बॉक्सिकता अंतराल के समान सेट पर अंतराल ग्राफ़ की न्यूनतम संख्या है, जैसे कि अंतराल ग्राफ़ के किनारों के सेट का प्रतिच्छेदन G है। प्रत्येक बाहरी ग्राफ़ में अधिकतम दो पर बॉक्सिकिटी होती है, और प्रत्येक प्लेनर ग्राफ में अधिक से अधिक तीन में बॉक्सिकिटी होती है। यदि एक द्विदलीय ग्राफ में बॉक्सिकिटी दो है, तो इसे विमान में अक्ष-समानांतर रेखा खंडों के प्रतिच्छेदन ग्राफ के रूप में दर्शाया जा सकता है।

Adiga, Bhowmick & Chandran (2011) ने साबित किया कि द्विदलीय ग्राफ G की बॉक्सिकता ऊंचाई के आदेश आयाम के एक कारक 2 के भीतर है- दो आंशिक रूप से G से जुड़े सेट का आदेश इस प्रकार है: न्यूनतम तत्वों का सेट G के एक आंशिक सेट से मेल खाता है, का सेट अधिकतम तत्व G के दूसरे पक्षीय सेट से मेल खाते हैं, और दो तत्व तुलनीय हैं यदि संबंधित कोने G में आसन्न हैं। समान रूप से, ऊंचाई-दो आंशिक रूप से आदेशित सेट P का ऑर्डर आयाम तुलनात्मकता के बॉक्सिकता के कारक 2 के भीतर है P का ग्राफ (जो द्विदलीय है, चूँकि P की ऊँचाई दो है)।

एल्गोरिथम परिणाम

कई ग्राफ़ समस्याओं को हल किया जा सकता है या बाउंड बॉक्सिकिटी वाले ग्राफ़ के लिए अन्य ग्राफ़ की तुलना में अधिक कुशलता से हल किया जा सकता है; उदाहरण के लिए, बाउंड बॉक्सिकिटी वाले ग्राफ़ के लिए बहुपद समय में अधिकतम क्लिक समस्या को हल किया जा सकता है। कुछ अन्य ग्राफ़ समस्याओं के लिए, एक कम-आयामी बॉक्स प्रतिनिधित्व ज्ञात होने पर एक कुशल समाधान या सन्निकटन पाया जा सकता है। हालाँकि, ऐसा प्रतिनिधित्व खोजना मुश्किल हो सकता है: यह परीक्षण करने के लिए एनपी-पूर्ण है कि क्या किसी दिए गए ग्राफ की बॉक्सिकता कुछ दिए गए मान K पर है, यहां तक ​​​​कि K = 2 के लिए भी। Chandran, Francis & Sivadasan (2010) ग्राफ के डिग्री (ग्राफ सिद्धांत) के लॉगरिदमिक कारक के भीतर एक आयाम के साथ, बक्से के चौराहे ग्राफ के रूप में मनमाना ग्राफ के प्रतिनिधित्व को खोजने के लिए एल्गोरिदम का वर्णन करें; यह परिणाम ग्राफ़ की बॉक्सिकिटी पर एक ऊपरी सीमा प्रदान करता है।

अपने प्राकृतिक पैरामीटर के लिए कठोर होने के बावजूद, बॉक्सिकिटी पैरामीटरयुक्त जटिलता है। इनपुट ग्राफ के वर्टेक्स कवर नंबर द्वारा पैरामीटर किए जाने पर फिक्स्ड-पैरामीटर ट्रैक्टेबल।

सीमा

यदि किसी ग्राफ़ G ग्राफ़ में m किनारे हैं, तो: $box(G)=O({\sqrt {m\cdot \log(m)}})$. यदि एक ग्राफ G k-Degeneracy (ग्राफ़ सिद्धांत) है (के साथ $k\geq 2$) और n शीर्ष हैं, तो G में बॉक्सिकता है $box(G)\leq (k+2)\lceil 2e\log n\rceil$. यदि ग्राफ़ G का ग्राफ माइनर के रूप में शीर्षों पर कोई पूर्ण ग्राफ़ नहीं है, तो $box(G)=O(t^{2}\log t)$ जबकि ग्राफ़ माइनर के रूप में और बॉक्सिकिटी के साथ टी कोने पर कोई पूर्ण ग्राफ़ नहीं है $\Omega (t{\sqrt {\log t}})$. विशेष रूप से, किसी भी ग्राफ G में बॉक्सीसिटी होती है $box(G)=O(\mu (G)^{2}\log \mu (G))$, कहाँ $\mu (G)$ कॉलिन डी वेर्डिएर ग्राफ इनवेरिएंट को दर्शाता है | जी का कॉलिन डी वेर्डिएर इनवेरिएंट।

संबंधित ग्राफ़ इनवेरिएंट्स

• घनापन को उसी तरह से परिभाषित किया जाता है जैसे कि बॉक्सिकिटी लेकिन हाइपररेक्टैंगल्स के बजाय एक्सिस-पैरेलल हाइपरक्यूब्स के साथ। बॉक्सिकिटी क्यूबिकिटी का एक सामान्यीकरण है।
• गोलाकारता (ग्राफ़ सिद्धांत) को उसी तरह से परिभाषित किया जाता है जैसे कि बॉक्सिकता लेकिन इकाई-व्यास वाले क्षेत्रों के साथ।

संदर्भ

• Adiga, Abhijin; Bhowmick, Diptendu; Chandran, L. Sunil (2011), "Boxicity and Poset Dimension", SIAM Journal on Discrete Mathematics, 25 (4): 1687–1698, arXiv:1003.2357, doi:10.1137/100786290, S2CID 12656133.
• Adiga, Abhijin; Chandran, L. Sunil; Mathew, Rogers (2014), "Cubicity, Degeneracy, and Crossing Number", European Journal of Combinatorics, 35: 2–12, arXiv:1105.5225, doi:10.1016/j.ejc.2013.06.021, S2CID 2069078.
• 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 (PDF), Lecture Notes in Computer Science, vol. 6506, pp. 366–377, doi:10.1007/978-3-642-17517-6_33, archived from the original (PDF) on 2017-08-30, retrieved 2018-01-22
• 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, hdl:1874/18908.
• Bellantoni, Stephen J.; Ben-Arroyo Hartman, Irith; Przytycka, Teresa; Whitesides, Sue (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.; Ramaswami, S. (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, arXiv:cs.DM/0605013, doi:10.1007/s00453-008-9163-5, MR 2576537, S2CID 17838951.
• Chandran, L. Sunil; Sivadasan, Naveen (2007), "Boxicity and treewidth", Journal of Combinatorial Theory, Series B, 97 (5): 733–744, arXiv:math.CO/0505544, doi:10.1016/j.jctb.2006.12.004, S2CID 9854207.
• 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.
• Cozzens, M. B. (1981), Higher and Multidimensional Analogues of Interval Graphs, Ph.D. thesis, Rutgers University.
• Esperet, Louis (2016), "Boxicity and topological invariants", European Journal of Combinatorics, 51: 495–499, arXiv:1503.05765, doi:10.1016/j.ejc.2015.07.020, S2CID 5548385.
• Esperet, Louis; Wiechert, Veit (2018), "Boxicity, poset dimension, and excluded minors", Electronic Journal of Combinatorics, 25 (4): #P4.51, arXiv:1804.00850, doi:10.37236/7787, S2CID 119148637.
• 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. (ed.), 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.