बॉक्सिसिटी

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

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

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

उदाहरण

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

रॉबर्ट्स (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-डीजेनेरसी (ग्राफ़ सिद्धांत) है ($k\geq 2$ के साथ) और n शीर्ष हैं, तो G में $box(G)\leq (k+2)\lceil 2e\log n\rceil$ बॉक्सिकता है।

यदि ग्राफ़ G का ग्राफ अवयस्क के रूप में शीर्षों पर कोई पूर्ण ग्राफ़ नहीं है, तो $box(G)=O(t^{2}\log t)$ जबकि ग्राफ़ अवयस्क के रूप में और बॉक्सिसिटी के साथ 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.