Planarity testing
ग्राफ सिद्धांत में, समतलीयता परीक्षण समस्या यह परीक्षण करने की एल्गोरिथमिक समस्या है कि क्या दिया गया ग्राफ एक समतलीय ग्राफ है (यानी, क्या इसे किनारे के प्रतिच्छेदन के बिना समतल में खींचा जा सकता है)। कंप्यूटर विज्ञान में यह एक अच्छी तरह से अध्ययन की गई समस्या है जिसके लिए कई व्यावहारिक एल्गोरिदम सामने आए हैं, जिनमें से कई नए डेटा संरचनाओं का लाभ उठा रहे हैं। इनमें से अधिकांश विधियाँ ओ (एन) समय (रैखिक समय) में काम करती हैं, जहाँ एन ग्राफ में किनारों (या शीर्षों) की संख्या है, जो स्पर्शोन्मुख रूप से इष्टतम है। केवल एक एकल बूलियन मूल्य होने के बजाय, एक समतलीय परीक्षण एल्गोरिथ्म का आउटपुट एक समतलीय ग्राफ एम्बेडिंग हो सकता है, यदि ग्राफ समतलीय है, या समतलीयता के लिए एक बाधा जैसे कि कुराटोव्स्की उपग्राफ यदि नहीं है। प्लेनेरिटी क्राइटेरिया प्लेनेरिटी टेस्टिंग एल्गोरिदम आमतौर पर ग्राफ थ्योरी में प्रमेयों का लाभ उठाते हैं जो प्लेनर ग्राफ के सेट को ग्राफ ड्राइंग से स्वतंत्र होने के संदर्भ में चिह्नित करते हैं। इनमें कुराटोव्स्की की प्रमेय शामिल है कि एक ग्राफ समतल है यदि और केवल तभी जब इसमें एक उपग्राफ नहीं है जो K5 (पांच शीर्षों पर पूरा ग्राफ) या K3,3 (उपयोगिता ग्राफ, छह शीर्षों पर एक पूर्ण द्विदलीय ग्राफ, जिनमें से तीन अन्य तीन में से प्रत्येक से जुड़ते हैं) का एक उपखंड है। वैगनर की प्रमेय है कि एक ग्राफ समतल है यदि और केवल तभी जब इसमें एक छोटा (संकुचन का उपग्राफ) नहीं होता है जो K5 या K3,3 के लिए समरूप है। फ्रेसिक्स-रोसेनस्टीहल समतलीयता मानदंड, एक गहराई-प्रथम खोज वृक्ष में किनारों के बाएं-दाएं क्रम के संदर्भ में समतलीय ग्राफ की विशेषता है। फ्रेसिक्स-रोसेनस्टीहल समतलीयता मानदंड का उपयोग सीधे समतलीयता परीक्षण के लिए एल्गोरिदम के हिस्से के रूप में किया जा सकता है, जबकि कुराटोव्स्की और वैगनर के प्रमेयों में अप्रत्यक्ष अनुप्रयोग हैंः यदि एक एल्गोरिदम दिए गए ग्राफ के भीतर के5 या के3,3 की एक प्रति पा सकता है, तो यह सुनिश्चित किया जा सकता है कि इनपुट ग्राफ समतलीय नहीं है और अतिरिक्त गणना के बिना वापस आ जाता है। अन्य समतलीयता मानदंड, जो गणितीय रूप से समतलीय ग्राफ की विशेषता रखते हैं, लेकिन समतलीयता परीक्षण एल्गोरिदम के लिए कम केंद्रीय हैं, उनमें शामिल हैंः व्हिटनी की समतलीयता मानदंड कि एक ग्राफ समतल है यदि और केवल तभी जब इसका ग्राफिक मैट्रायड भी भौगोलिक हो, मैक लेन की समतलीयता मानदंड जो समतलीय ग्राफ को उनके चक्र स्थानों के आधारों द्वारा चिह्नित करता है, श्नाइडर की प्रमेय जो एक संबंधित आंशिक क्रम के क्रम आयाम द्वारा समतलीय ग्राफ की विशेषता बताती है, और वर्णक्रमीय ग्राफ सिद्धांत का उपयोग करके कॉलिन डी वर्डीयर की समतलीयता मानदंड। एल्गोरिदम पाथ एडिशन मेथड हॉपक्राफ्ट और टार्जन की क्लासिक पाथ एडिशन मेथड 1974 में पहली बार प्रकाशित रैखिक-समय प्लेनेरिटी परीक्षण एल्गोरिदम थी। हॉपक्राफ्ट और टार्जन के एल्गोरिदम का कार्यान्वयन मेहल्हॉर्न, मुतज़ेल और नाहर द्वारा कुशल डेटा प्रकारों और एल्गोरिदम के पुस्तकालय में प्रदान किया गया है। 2012 में, टेलर ने इस एल्गोरिथ्म को द्वि-संयोजित घटकों के समतल एम्बेडिंग के लिए चक्रीय किनारे-क्रम के सभी क्रमपरिवर्तन उत्पन्न करने के लिए विस्तारित किया। वर्टेक्स जोड़ विधि वर्टेक्स जोड़ विधियाँ एक डेटा संरचना को बनाए रखते हुए काम करती हैं जो दिए गए ग्राफ के एक प्रेरित उपग्राफ के संभावित एम्बेडिंग का प्रतिनिधित्व करती है, और इस डेटा संरचना में एक बार में एक शीर्ष जोड़ती है। ये विधियाँ 1967 में लेम्पेल, इवन और सेडरबाम द्वारा परिकल्पित एक अक्षम ओ (एन2) विधि के साथ शुरू हुईं। इसे इवन और टार्जन द्वारा सुधार किया गया था, जिन्होंने एस, टी-नंबरिंग चरण के लिए एक रैखिक-समय समाधान पाया, और बूथ और ल्यूकर द्वारा, जिन्होंने पीक्यू ट्री डेटा संरचना विकसित की। इन सुधारों के साथ यह रैखिक-समय है और व्यवहार में पथ जोड़ विधि से बेहतर प्रदर्शन करता है। इस विधि को एक प्लेनर ग्राफ के लिए एक प्लेनर एम्बेडिंग (ड्राइंग) की कुशलता से गणना करने की अनुमति देने के लिए भी विस्तारित किया गया था। 1999 में, शिह और सू ने पी. सी. वृक्ष (पी. क्यू. वृक्ष का एक जड़हीन संस्करण) और शीर्षों के गहराई-पहले खोज वृक्ष के एक पोस्टऑर्डर ट्रैवर्सल का उपयोग करके इन विधियों को सरल बनाया। 2004 में, जॉन बॉयर और वेंडी मायर्वोल्ड ने एक सरलीकृत ओ (एन) एल्गोरिथ्म विकसित किया, जो मूल रूप से पीक्यू ट्री विधि से प्रेरित था, जो पीक्यू ट्री से छुटकारा दिलाता है और यदि संभव हो तो एक प्लेनर एम्बेडिंग की गणना करने के लिए एज एडिशन का उपयोग करता है। अन्यथा, एक कुराटोव्स्की उपखंड (के5 या के3,3 में से) की गणना की जाती है। यह आज के दो वर्तमान अत्याधुनिक एल्गोरिदम में से एक है (दूसरा डी फ्रेसिक्स, ओसोना डी मेंडेज़ और रोसेनस्टीहल का प्लेनेरिटी परीक्षण एल्गोरिदम है)। बोयर और मायर्वोल्ड प्लेनेरिटी परीक्षण के प्रारंभिक संस्करण के साथ एक प्रयोगात्मक तुलना के लिए देखें। इसके अलावा, बॉयर-मिरवोल्ड परीक्षण को उत्पादन के आकार पर निर्भर एक चालू समय में एक गैर-समतल इनपुट ग्राफ के कई कुराटोव्स्की उपखंडों को निकालने के लिए विस्तारित किया गया था। समतलीयता परीक्षण और कई कुराटोव्स्की उपखंडों के निष्कर्षण के लिए स्रोत कोड सार्वजनिक रूप से उपलब्ध है। 1980 के दशक में विलियमसन द्वारा विकसित किए गए एल्गोरिदम जो शीर्षों में रैखिक समय में कुराटोव्स्की सबग्राफ का पता लगाते हैं। निर्माण अनुक्रम विधि एक अलग विधि जी के प्रत्येक 3-जुड़े घटक (और इसलिए स्वयं जी का एक समतल एम्बेडिंग) के समतलीय एम्बेडिंग को बढ़ाने के लिए 3-जुड़े ग्राफ के एक प्रेरक निर्माण का उपयोग करती है। निर्माण के4 से शुरू होता है और इसे इस तरह से परिभाषित किया गया है कि पूर्ण घटक के रास्ते में प्रत्येक मध्यवर्ती ग्राफ फिर से 3-जुड़ा हुआ है। चूँकि इस तरह के ग्राफ में एक अद्वितीय एम्बेडिंग होती है (फ़्लिपिंग और बाहरी चेहरे की पसंद तक), अगला बड़ा ग्राफ, यदि अभी भी समतल है, तो पूर्व ग्राफ का एक परिष्करण होना चाहिए। यह प्लेनेरिटी परीक्षण को केवल प्रत्येक चरण के लिए परीक्षण करने के लिए कम करने की अनुमति देता है कि क्या अगले जोड़े गए किनारे के दोनों छोर वर्तमान एम्बेडिंग के बाहरी चेहरे में हैं। जबकि यह अवधारणात्मक रूप से बहुत सरल है (और रैखिक चलने का समय देता है), विधि स्वयं निर्माण अनुक्रम खोजने की जटिलता से ग्रस्त है। डायनेमिक एल्गोरिदम प्लेनेरिटी परीक्षण का अध्ययन डायनेमिक एल्गोरिदम मॉडल में किया गया है, जिसमें एक समस्या का उत्तर (इस मामले में प्लेनेरिटी) बनाए रखा जाता है क्योंकि ग्राफ स्थानीय अद्यतन से गुजरता है, आमतौर पर किनारों को डालने/हटाने के रूप में। किनारे-आगमन के मामले में, ला पॉट्रे के कारण एक असंवेदनशील रूप से तंग व्युत्क्रम-एकरमैन फ़ंक्शन अद्यतन-समय एल्गोरिदम है, जो डि बतिस्ता, तमासिया और वेस्टब्रुक द्वारा एल्गोरिदम में सुधार करता है। पूरी तरह से गतिशील मामले में जहां किनारों को डाला और हटा दिया जाता है, वहां एक लघुगणक अद्यतन-समय होता है जो पैट्रास्कु और डेमाइन द्वारा कम बाध्य होता है, और होल्म और रोटेनबर्ग द्वारा एक बहुगणक अद्यतन-समय एल्गोरिदम होता है, जो एपस्टीन, गैलील, इटालियानो, सारनाक और स्पेंसर द्वारा उप-रैखिक अद्यतन-समय एल्गोरिदम में सुधार करता है। प्लैनर ग्राफ ग्राफ सिद्धांत में कम्प्यूटेशनल समस्याओं के संदर्भ