आउटरप्लानर ग्राफ

एक मैक्सिमम आउटरप्लानर ग्राफ और इसका 3-कलरिंग

पूरा ग्राफ के₄ सबसे छोटा प्लानर ग्राफ है जो आउटरप्लानर नहीं है।

ग्राफ़ सिद्धांत में, एक आउटरप्लानर ग्राफ़ एक ग्राफ़ होता है जिसमें एक प्लैनर आरेखण होता है जिसके लिए सभी कोने आरेखण के बाहरी चेहरे से संबंधित होते हैं।

आउटर प्लेनर ग्राफ को दो वर्जित अवयस्क K4 और K2,3, या उनके कॉलिन डी वेर्डिएर ग्राफ़ इनवेरिएंट द्वारा (प्लैनर ग्राफ़ के लिए वैगनर के प्रमेय के अनुरूप) चित्रित किया जा सकता है।

उनके पास हैमिल्टनियन चक्र हैं यदि और केवल यदि वे द्विसंबद्ध हैं, तो इस मामले में बाहरी चेहरा अद्वितीय हैमिल्टनियन चक्र बनाता है। प्रत्येक आउटरप्लानर ग्राफ 3-रंगीन है, और अधिकतम 2 में गिरावट और पेड़ की चौड़ाई है।

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

इतिहास

बाह्यतलीय रेखांकन का सर्वप्रथम अध्ययन और नामकरण किसके द्वारा किया गया था? चार्ट्रैंड & एंड हैरी (1967), एक आधार ग्राफ की दो प्रतियों को जोड़ने के लिए एक परिपूर्ण मिलान का उपयोग करके बनाए गए रेखांकन की योजना का निर्धारण करने की समस्या के संबंध में (उदाहरण के लिए, कई सामान्यीकृत पीटरसन ग्राफ एक चक्र ग्राफ की दो प्रतियों से इस तरह से बनते हैं) . जैसा कि उन्होंने दिखाया, जब बेस ग्राफ़ द्विसंबद्ध ग्राफ़ होता है, तो इस तरह से निर्मित एक ग्राफ़ प्लेनर होता है, अगर और केवल अगर इसका आधार ग्राफ़ आउटरप्लानर होता है और मिलान इसके बाहरी चक्र का एक डायहेड्रल समूह क्रमपरिवर्तन बनाता है। चार्ट्रैंड और हैरी ने आउटरप्लानर ग्राफ़ के लिए कुराटोव्स्की के प्रमेय का एक एनालॉग भी साबित किया, कि एक ग्राफ़ आउटरप्लानर है अगर और केवल अगर इसमें दो ग्राफ़ K में से एक का होमोमोर्फिज़्म (ग्राफ़ सिद्धांत) शामिल नहीं है₄ या के_2,3.

बेस ग्राफ की दो प्रतियों को जोड़ने के लिए एक परिपूर्ण मिलान का उपयोग करके बनाए गए ग्राफ की योजना का निर्धारण करने की समस्या के संबंध में, चार्ट्रैंड & एंड हैरी (1967) द्वारा आउटरप्लानर ग्राफ़ का अध्ययन और नामकरण किया गया था (उदाहरण के लिए, सामान्यीकृत पीटरसन ग्राफ में से कई एक चक्र ग्राफ की दो प्रतियों से इस प्रकार बनते हैं)। जैसा कि उन्होंने दिखाया, जब बेस ग्राफ़ द्विसंबद्ध ग्राफ़ होता है, तो इस तरह से निर्मित एक ग्राफ़ प्लेनर होता है, अगर और केवल अगर इसका आधार ग्राफ़ आउटरप्लानर होता है और मिलान इसके बाहरी चक्र का एक डायहेड्रल समूह क्रमपरिवर्तन बनाता है। चार्ट्रैंड और हैरी ने आउटरप्लानर ग्राफ़ के लिए कुराटोव्स्की के प्रमेय का एक एनालॉग भी साबित किया, कि एक ग्राफ़ आउटरप्लानर है अगर और केवल अगर इसमें दो ग्राफ़ K में से एक का होमोमोर्फिज़्म (ग्राफ़ सिद्धांत) शामिल नहीं है₄ या के_2,3.

परिभाषा और लक्षण वर्णन

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

निषिद्ध रेखांकन

आउटरप्लानर ग्राफ़ में कुराटोव्स्की के प्रमेय और प्लेनर ग्राफ़ के लिए वैगनर के प्रमेय के अनुरूप एक वर्जित ग्राफ़ विशेषता है: एक ग्राफ़ आउटरप्लानर है अगर और केवल अगर इसमें पूर्ण ग्राफ़ K का होमोमोर्फिज़्म (ग्राफ़ सिद्धांत) शामिल नहीं है₄ या पूर्ण द्विदलीय ग्राफ K_2,3. वैकल्पिक रूप से, एक ग्राफ़ बाहरीप्लानर है अगर और केवल अगर इसमें के शामिल नहीं है₄ या के_2,3 एक नाबालिग (ग्राफ सिद्धांत) के रूप में, किनारों को हटाकर और अनुबंध करके इससे प्राप्त एक ग्राफ। एक त्रिभुज-मुक्त ग्राफ़ बाह्यप्लानर है यदि और केवल यदि इसमें K का उपखंड शामिल नहीं है_2,3.

कॉलिन डी वर्डीयर अपरिवर्तनीय

एक ग्राफ़ आउटरप्लानर होता है अगर और केवल अगर इसका कॉलिन डी वेर्डिएर ग्राफ़ इनवेरिएंट अधिकतम दो हो। कॉलिन डी वेर्डिएर के अधिकांश एक, तीन, या चार पर अपरिवर्तनीय होने के समान तरीके से दर्शाए गए रेखांकन क्रमशः रैखिक वन, समतल रेखांकन और लिंक रहित एम्बेडिंग।

गुण

बाइकनेक्टिविटी और हैमिल्टनिस

एक बाहरी प्लैनर ग्राफ़ द्विसंबद्ध ग्राफ़ है यदि और केवल अगर ग्राफ़ के बाहरी चेहरे दोहराए गए शिखर के बिना एक चक्र (ग्राफ़ सिद्धांत) बनाते हैं। एक आउटरप्लानर ग्राफ हैमिल्टनियन चक्र है अगर और केवल अगर यह द्विसंबद्ध है; इस मामले में, बाहरी चेहरा अद्वितीय हैमिल्टनियन चक्र बनाता है। अधिक आम तौर पर, एक बाहरी प्लैनर ग्राफ में सबसे लंबे चक्र का आकार इसके सबसे बड़े द्विसंबद्ध घटक में शीर्षों की संख्या के समान होता है। इस कारण से हेमिल्टनियन चक्रों और बाह्यप्लानर ग्राफों में सबसे लंबे चक्रों को रैखिक समय में हल किया जा सकता है, मनमाना ग्राफों के लिए इन समस्याओं की एनपी-पूर्णता के विपरीत।

प्रत्येक अधिकतम बाहरी समतलीय ग्राफ हैमिल्टनसिटी की तुलना में एक मजबूत स्थिति को संतुष्ट करता है: यह पैनसाइक्लिक ग्राफ है, जिसका अर्थ है कि प्रत्येक शीर्ष v और प्रत्येक k के लिए तीन से लेकर ग्राफ में कोने की संख्या तक, एक लंबाई-k चक्र होता है जिसमें v होता है। A इस लंबाई का चक्र एक त्रिकोण को बार-बार हटाकर पाया जा सकता है जो शेष ग्राफ़ से एक किनारे से जुड़ा हुआ है, जैसे कि हटाया गया शीर्ष v नहीं है, जब तक कि शेष ग्राफ़ के बाहरी फलक की लंबाई k न हो। एक प्लानर ग्राफ आउटरप्लानर है अगर और केवल अगर इसके प्रत्येक बायकनेक्टेड घटक आउटरप्लानर हैं।

रंग

सभी लूपलेस आउटरप्लानर ग्राफ केवल तीन रंगों का उपयोग करके ग्राफ रंग हो सकते हैं; इस तथ्य को वैक्लाव च्वाटल के सरलीकृत प्रमाण में प्रमुखता से दिखाया गया है। च्वातल की आर्ट गैलरी प्रमेय द्वारा Fisk (1978). एक लालची रंग एल्गोरिथ्म द्वारा रैखिक समय में एक 3-रंग पाया जा सकता है जो अधिकतम दो डिग्री (ग्राफ सिद्धांत) के किसी भी शीर्ष को हटा देता है, शेष ग्राफ को पुनरावर्ती रूप से रंग देता है, और फिर हटाए गए शीर्ष को रंगों से भिन्न रंग के साथ वापस जोड़ता है। इसके दो पड़ोसी।

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

अन्य गुण

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

रेखांकन के संबंधित परिवार

कैक्टस ग्राफ। कैक्टि बाहरी प्लैनर ग्राफ का एक उपवर्ग बनाते हैं।

हर आउटरप्लानर ग्राफ एक प्लेनर ग्राफ है। प्रत्येक आउटरप्लानर ग्राफ भी एक श्रृंखला-समानांतर ग्राफ का एक सबग्राफ है। हालाँकि, सभी प्लानर श्रृंखला-समानांतर ग्राफ़ आउटरप्लानर नहीं हैं। पूर्ण द्विदलीय ग्राफ K_2,3 प्लानर और सीरीज़-समानांतर है लेकिन आउटरप्लानर नहीं है। दूसरी ओर, पूरा ग्राफ K₄ प्लानर है लेकिन न तो श्रृंखला-समानांतर है और न ही आउटरप्लानर। हर पेड़ (ग्राफ थ्योरी) और हर कैक्टस ग्राफ आउटरप्लानर हैं।

एक एम्बेडेड आउटरप्लानर ग्राफ का तलीय दोहरी ग्राफ (वह ग्राफ जिसमें एम्बेडिंग के प्रत्येक बंधे हुए चेहरे के लिए एक शीर्ष है, और आसन्न बंधे चेहरों की हर जोड़ी के लिए एक किनारा है) एक जंगल है, और एक हालीन ग्राफ का कमजोर प्लानर डुअल एक है आउटरप्लानर ग्राफ। एक प्लानर ग्राफ आउटरप्लानर है अगर और केवल अगर इसकी कमजोर दोहरी एक जंगल है, और यह हैलिन है अगर और केवल अगर इसकी कमजोर दोहरी बाइकनेक्टेड और आउटरप्लानर है। आउटरप्लानरिटी की डिग्री की धारणा है। एक ग्राफ़ का 1-आउटरप्लानर एम्बेडिंग एक आउटरप्लानर एम्बेडिंग के समान है। k > 1 के लिए एक प्लानर एम्बेडिंग को K-आउटरप्लानर ग्राफ|k-आउटरप्लानर कहा जाता है यदि बाहरी फलक पर वर्टिकल को हटाने से (k − 1)-आउटरप्लानर एम्बेडिंग होता है। एक ग्राफ के-आउटरप्लानर है यदि इसमें के-आउटरप्लानर एम्बेडिंग है। एक 1-प्लानर ग्राफ़#सामान्यीकरण और संबंधित अवधारणाएं|बाहरी-1-प्लानर ग्राफ़, 1-प्लानर ग्राफ़ के समान रूप से, डिस्क की सीमा पर शीर्षों के साथ, और प्रति किनारे अधिकतम एक क्रॉसिंग के साथ डिस्क में खींचा जा सकता है।

प्रत्येक अधिक से अधिक बाह्यप्लानर ग्राफ एक तारकीय ग्राफ है। प्रत्येक अधिकतम बाह्यप्लानर ग्राफ एक साधारण बहुभुज का दृश्यता ग्राफ है। मैक्सिमल आउटरप्लानर ग्राफ़ भी बहुभुज त्रिभुजों के ग्राफ़ के रूप में बनते हैं। वे k-वृक्ष | 2-ट्रीज़, सीरीज़-पैरेलल ग्राफ़ और कॉर्डल ग्राफ़ के उदाहरण हैं।

हर आउटरप्लानर ग्राफ एक सर्कल ग्राफ है, एक सर्कल के कॉर्ड्स के सेट का इंटरसेक्शन ग्राफ।

संदर्भ

• Baker, Brenda S. (1994), "Approximation algorithms for NP-complete problems on planar graphs", Journal of the ACM, 41 (1): 153–180, doi:10.1145/174644.174650, S2CID 9706753.
• Boza, Luis; Fedriani, Eugenio M.; Núñez, Juan (2004), "The problem of outer embeddings in pseudosurfaces", Ars Combinatoria, 71: 79–91.
• Boza, Luis; Fedriani, Eugenio M.; Núñez, Juan (2004), "Obstruction sets for outer-bananas-surface graphs", Ars Combinatoria, 73: 65–77.
• Boza, Luis; Fedriani, Eugenio M.; Núñez, Juan (2006), "Uncountable graphs with all their vertices in one face", Acta Mathematica Hungarica, 112 (4): 307–313, doi:10.1007/s10474-006-0082-0, S2CID 123241658.
• Boza, Luis; Fedriani, Eugenio M.; Núñez, Juan (2010), "Outer-embeddability in certain pseudosurfaces arising from three spheres", Discrete Mathematics, 310 (23): 3359–3367, doi:10.1016/j.disc.2010.07.027.
• Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics, ISBN 0-89871-432-X.
• Chartrand, Gary; Harary, Frank (1967), "Planar permutation graphs", Annales de l'Institut Henri Poincaré B, 3 (4): 433–438, MR 0227041.
• Diestel, Reinhard (2000), Graph Theory, Graduate Texts in Mathematics, vol. 173, Springer-Verlag, p. 107, ISBN 0-387-98976-5.
• El-Gindy, H. (1985), Hierarchical decomposition of polygons with applications, Ph.D. thesis, McGill University. As cited by Brandstädt, Le & Spinrad (1999).
• Felsner, Stefan (2004), Geometric graphs and arrangements: some chapters from combinational geometry, Vieweg+Teubner Verlag, p. 6, ISBN 978-3-528-06972-8.
• Fiorini, Stanley (1975), "On the chromatic index of outerplanar graphs", Journal of Combinatorial Theory, Series B, 18 (1): 35–38, doi:10.1016/0095-8956(75)90060-X.
• Fisk, Steve (1978), "A short proof of Chvátal's watchman theorem", Journal of Combinatorial Theory, Series B, 24 (3): 374, doi:10.1016/0095-8956(78)90059-X.
• Fleischner, Herbert J.; Geller, D. P.; Harary, Frank (1974), "Outerplanar graphs and weak duals", Journal of the Indian Mathematical Society, 38: 215–219, MR 0389672.
• Kane, Vinay G.; Basu, Sanat K. (1976), "On the depth of a planar graph", Discrete Mathematics, 14 (1): 63–67, doi:10.1016/0012-365X(76)90006-6.
• Li, Ming-Chu; Corneil, Derek G.; Mendelsohn, Eric (2000), "Pancyclicity and NP-completeness in planar graphs", Discrete Applied Mathematics, 98 (3): 219–225, doi:10.1016/S0166-218X(99)00163-8.
• Lick, Don R.; White, Arthur T. (1970), "k[[Category: Templates Vigyan Ready]]-degenerate graphs", Canadian Journal of Mathematics, 22 (5): 1082–1096, doi:10.4153/CJM-1970-125-1 {{citation}}: URL–wikilink conflict (help).
• Lin, Yaw-Ling; Skiena, Steven S. (1995), "Complexity aspects of visibility graphs", International Journal of Computational Geometry and Applications, 5 (3): 289–312, doi:10.1142/S0218195995000179.
• Proskurowski, Andrzej; Sysło, Maciej M. (1986), "Efficient vertex-and edge-coloring of outerplanar graphs", SIAM Journal on Algebraic and Discrete Methods, 7: 131–136, doi:10.1137/0607016.
• Scheinerman, E. R. (1984), Intersection Classes and Multiple Intersection Parameters of a Graph, Ph.D. thesis, Princeton University. As cited by Brandstädt, Le & Spinrad (1999).
• Sysło, Maciej M. (1979), "Characterizations of outerplanar graphs", Discrete Mathematics, 26 (1): 47–53, doi:10.1016/0012-365X(79)90060-8.
• Sysło, Maciej M.; Proskurowski, Andrzej (1983), "On Halin graphs", Graph Theory: Proceedings of a Conference held in Lagów, Poland, February 10–13, 1981, Lecture Notes in Mathematics, vol. 1018, Springer-Verlag, pp. 248–256, doi:10.1007/BFb0071635.
• Unger, Walter (1988), "On the k-colouring of circle-graphs", Proc. 5th Symposium on Theoretical Aspects of Computer Science (STACS '88), Lecture Notes in Computer Science, vol. 294, Springer-Verlag, pp. 61–72, doi:10.1007/BFb0035832.
• Wessel, W.; Pöschel, R. (1985), "On circle graphs", in Sachs, Horst (ed.), Graphs, Hypergraphs and Applications: Proceedings of the Conference on Graph Theory Held in Eyba, October 1st to 5th, 1984, Teubner-Texte zur Mathematik, vol. 73, B.G. Teubner, pp. 207–210. As cited by Unger (1988).

बाहरी संबंध

• Outerplanar graphs at the Information System on Graph Classes and Their Inclusions
• Weisstein, Eric W. "Outplanar Graph". MathWorld.