Left-right planarity test
ग्राफ सिद्धांत में, गणित की एक शाखा, लेफ्ट-राइट प्लेनेरिटी टेस्ट या डी फ्रेसिक्स-रोसेनस्टील प्लेनेरिटी क्राइटेरियन, डेप्थ-फर्स्ट सर्च ट्री के गुणों के आधार पर प्लेनर ग्राफ का एक लक्षण वर्णन है, जिसे पैट्रिस ओसोना डी मेंडेज़ द्वारा प्रकाशित और उनके द्वारा रैखिक समय प्लेनेरिटी परीक्षण एल्गोरिदम विकसित करने के लिए उपयोग किया जाता है। 2003 में छह प्लेनेरिटी परीक्षण एल्गोरिदम की प्रायोगिक तुलना में, यह परीक्षण किए गए सबसे तेज़ एल्गोरिदम में से एक था। टी-समान और टी-विपरीत किनारे ग्राफ जी की किसी भी गहराई-पहली खोज के लिए, पहली बार एक शीर्ष की खोज करते समय सामने आने वाले किनारे जी के गहराई-पहले खोज पेड़ टी को परिभाषित करते हैं। यह एक ट्रेमॉक्स पेड़ है, जिसका अर्थ है कि शेष किनारे (कोट्री) प्रत्येक शीर्षों की एक जोड़ी को जोड़ते हैं जो टी में एक पूर्वज और वंशज के रूप में एक दूसरे से संबंधित हैं। कोट्री किनारों के जोड़े के बीच दो संबंधों को परिभाषित करने के लिए तीन प्रकार के पैटर्न का उपयोग किया जा सकता है, जिसे टी-समान और टी-विपरीत संबंध कहा जाता है। निम्नलिखित आकृतियों में, सरल वृत्त नोड्स शीर्षों का प्रतिनिधित्व करते हैं, दोहरे वृत्त नोड्स उप-वृक्षों का प्रतिनिधित्व करते हैं, मुड़े हुए खंड वृक्ष पथ का प्रतिनिधित्व करते हैं, और घुमावदार चाप कोट्री किनारों का प्रतिनिधित्व करते हैं। प्रत्येक पेड़ की जड़ आकृति के नीचे दिखाई गई है। पहली आकृति में, किनारों को लेबल किया गया है और टी-समान हैं, जिसका अर्थ है कि, पेड़ की जड़ के निकटतम अंतिम बिंदुओं पर, वे दोनों प्रत्येक समतल चित्र में पेड़ के एक ही तरफ होंगे। अगले दो आंकड़ों में, एक ही लेबल वाले किनारे टी-विपरीत हैं, जिसका अर्थ है कि वे प्रत्येक समतल चित्र में पेड़ के अलग-अलग किनारों पर होंगे। मान लीजिए कि G एक ग्राफ है और मान लीजिए कि T, G का एक ट्रेमॉक्स ट्री है। ग्राफ G समतल है यदि और केवल तभी जब G के कोट्री किनारों का दो वर्गों में विभाजन मौजूद है ताकि कोई भी दो किनारे एक ही वर्ग के हों यदि वे T-समान हैं और कोई भी दो किनारे अलग-अलग वर्गों के हों यदि वे T-विपरीत हैं। यह लक्षण वर्णन तुरंत एक (अक्षम) समतलता परीक्षण की ओर ले जाता हैः किनारों के सभी जोड़े के लिए निर्धारित करें कि क्या वे टी-समान या टी-विपरीत हैं, एक सहायक ग्राफ बनाएं जिसमें टी-समान किनारों के प्रत्येक जुड़े घटक के लिए एक शीर्ष और टी-विपरीत किनारों के प्रत्येक जोड़े के लिए एक किनारा हो, और जांच करें कि क्या यह सहायक ग्राफ द्विदलीय है। इस एल्गोरिथ्म को कुशल बनाने में टी-समान और टी-विपरीत जोड़े का एक उपसमुच्चय खोजना शामिल है जो इनपुट ग्राफ में सभी किनारे जोड़े के बीच संबंध निर्धारित किए बिना इस विधि को पूरा करने के लिए पर्याप्त है। संदर्भ आगे पढ़ने के लिए टोपोलॉजिकल ग्राफ सिद्धांत प्लानर ग्राफ