समतल आलेख

"त्रिकोणीय आलेख" redirects here. For पूर्ण आलेख के रेखा आलेख, see रेखा आलेख § दृढ़ता से नियमित और उत्तम रेखा आलेख. For त्रिकोणीय रेखांकन, see कॉर्डल आलेख. For डेटा आलेख तीन चरों में स्थापित किए गए, see टर्नेरी कथानक.

उदाहरण आलेख
तलीय	नॉनयोजना
File:Butterfly graph.svg तितली आलेख	File:Complete graph K5.svg संपूर्ण आलेख K5
File:CGK4PLN.svg संपूर्ण आलेख K4	File:Biclique K 3 3.svg उपयोगिता आलेख K3,3

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

प्रत्येक आलेख जो एक समतल पर खींचा जा सकता है, उसे त्रिविम प्रक्षेपण के माध्यम से गोले पर भी खींचा जा सकता है।

समतल आलेख संयोजक मानचित्रों या घुमाव प्रणाली द्वारा एन्कोड किया जा सकता है।

गोले पर संस्थानिक रूप से समतुल्य आलेखों का एक समतुल्य वर्ग, सामान्यतः आलेख सिद्धांत की अनुपस्थिति जैसी अतिरिक्त मान्यताओं के साथ, एक समतल मानचित्र कहलाता है। चूँकि समतल आलेख का एक बाहरी या असीमित फलन होता है (आलेख सिद्धांत), समतल मानचित्र के किसी भी फलन की कोई विशेष स्थिति नहीं होती है।

समतलीय आलेख किसी दिए गए जीनस (गणित) की सतह पर खींचे जाने योग्य आलेख के लिए सामान्यीकृत होते है। इस वाक्यांश में, समतलीय आलेख में आलेख जीनस 0 होता है, क्योंकि समतल (और गोला) जीनस 0 होती है। अन्य संबंधित विषयों के लिए आलेख अंतर्निहित देखें।

समतलीयता मानदंड

कुराटोव्स्की और वैगनर के प्रमेय

File:Tesseract graph nonplanar visual proof.svg

Proof without words that a hypercube graph is non-planar using Kuratowski's or Wagner's theorems and finding either K₅ (top) or K_3,3 (bottom) subgraphs

पोलैंड के गणितज्ञ काज़िमिर्ज़ कुराटोव्स्की ने निषिद्ध आलेख वर्णन के संदर्भ में समतल आलेख का एक वर्णन प्रदान किया था, जिसे अब कुराटोव्स्की के प्रमेय के रूप में जाना जाता है:

एक आलेख (असतत गणित) परिमित और अनंत आलेख समतल होते है यदि इसमें आलेख सिद्धांत की वाक्यांश सम्मलित नहीं होती है आलेख जो संपूर्ण आलेख का एक उपवर्ग (आलेख सिद्धांत) होता है K₅ या संपूर्ण आलेख K_3,3 (उपयोगिता आलेख)।

आलेख का एक उपवर्ग (आलेख सिद्धांत) किनारों में से उत्पन्न होता है (उदाहरण के लिए, एक किनारे को बदलना)। • —— • to • — • — • ) शून्य या अधिक होता है

Error creating thumbnail:

संख्या वाले आलेख का एक उदाहरण K₅ या K_3,3 उपआलेख. चूँकि, इसमें एक उपवर्ग सम्मलित है K_3,3 और इसलिए गैर-तलीय है।

उपवर्गों पर विचार करने के अतिरिक्त, वैगनर का प्रमेय लघु (आलेख सिद्धांत) से संबंधित होता है:

एक परिमित आलेख समतलीय होता है K₅ या K_3,3 एक लघु (आलेख सिद्धांत) होता है।

आलेख का एक लघु (आलेख सिद्धांत) एक उपआलेख एक किनारे को बार-बार एक शीर्ष में अनुबंधित करने से उत्पन्न होता है, जिसमें मूल अंत-शीर्ष का प्रत्येक गुण नए शीर्ष का गुण बन जाता है।

File:Kuratowski.gif

एक एनीमेशन जो दर्शाता है कि पीटरसन आलेख में मामूली समरूपी सम्मलित है K_3,3 आलेख, और इसलिए गैर-तलीय है

क्लॉस वैगनर (गणितज्ञ) ने पूछा कि क्या आलेख का कोई लघु-बंद वर्ग निषिद्ध लघु के एक सीमित समूह द्वारा निर्धारित किया जा सकता है। यह अब रॉबर्टसन-सेमुर प्रमेय के एक लंबी श्रृंखला में सिद्ध हुआ है। इस प्रमेय की भाषा में, K₅ और K_3,3परिमित समतलीय आलेख के वर्ग के लिए निषिद्ध अवयस्क होते है।

अन्य मानदंड

व्यवहार में, यह तय करने के लिए कि कोई दिया गया आलेख समतल है या नहीं, यह पता करने के लिए कुराटोस्की का उपयोग किया जाता है। चूँकि, इस समस्या के लिए तेज़ कलन विधि उपस्थित है: एक आलेख के लिए n शीर्ष, समय पर निर्धारित करना संभव है O(n) (रैखिक समय) आलेख समतलीय हो सकता है (तलीयता परीक्षण देखें)।

एक सरल, संपर्क, समतलीय आलेख के लिए v शीर्ष और e किनारे और f चेहरों के लिए निम्नलिखित सरल स्थितियाँ लागू होती है v ≥ 3:

• प्रमेय 1. e ≤ 3v – 6,
• प्रमेय 2. यदि लंबाई 3 का कोई चक्र नहीं है, तो e ≤ 2v – 4.
• प्रमेय 3. f ≤ 2v – 4.

इस अर्थ में, समतलीय आलेख विरल आलेख होते है, इसमें O(v) किनारे, अधिकतम से बिल्कुल छोटे O(v²) लेखाचित्र {{गणित|K_3,3}उदाहरण के लिए,} में 6 शीर्ष, 9 किनारे और लंबाई 3 का कोई चक्र नहीं है। इसलिए, प्रमेय 2 के अनुसार, यह समतल नहीं हो सकता है। यह प्रमेय समतलता के लिए आवश्यक स्थितिें प्रदान करते है, और इसलिए इसका उपयोग केवल यह सिद्ध करने के लिए किया जा सकता है कि आलेख समतल नहीं है। यदि प्रमेय 1 और 2 दोनों विफल हो जाते है, तो अन्य विधियों का उपयोग किया जा सकता है।

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

गुण

यूलर का सूत्र

Main article: यूलर विशेषता § समतल रेखांकन

यूलर के सूत्र में कहा गया है कि यदि एक परिमित, (आलेख सिद्धांत), समतलीय आलेख बिना किसी किनारे के समतल में खींचा जाता है, और v शीर्ष की संख्या है, e किनारों की संख्या है और f तो फलनों की संख्या है।

$v-e+f=2.$

उदाहरण के रूप में, ऊपर दिए गए तितली आलेख में, v = 5, e = 6 और f = 3.

सामान्यतः, यदि गुण सभी समतलीय आलेखों के लिए मान्य है f , आलेख में कोई भी परिवर्तन जो आलेख को समतल रखते हुए एक अतिरिक्त संकया प्राप्त होती है, v – e + f एक अपरिवर्तनीय. चूंकि गुण सभी आलेख के लिए मान्य है f = 2, गणितीय प्रेरण द्वारा यह सभी स्थितियों के लिए लागू होता है। यूलर के सूत्र को इस प्रकार भी सिद्ध किया जा सकता है: यदि आलेख एक ट्री नहीं है, v – e + f । यह तब तक दोहराएँ जब तक शेष आलेख एक ट्री न बन जाए, ट्री के पास है v = e + 1 और f = 1, और v – e + f = 2। ई., यूलर विशेषता 2 है।

एक परिमित में, आलेख सिद्धांत, सरल आलेख, समतल आलेख, (संभवतः बाहरी को छोड़कर) कम से कम तीन किनारों से घिरा होता है और प्रत्येक किनारा अधिकतम दो संख्याओ के पास होता है, यूलर के सूत्र का उपयोग करके, यह दिखाया जा सकता है कि ये आलेख इस अर्थ में विरल है यदि v ≥ 3:

$e\leq 3v-6.$

Error creating thumbnail:

एक नियमित द्वादशफ़लक का श्लेगल आरेख, एक उत्तल पॉलीहेड्रॉन से एक समतल आलेख बनाता है।

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

औसत डिग्री

एक से अधिक किनारों वाले जुड़े समतलीय आलेख असमानता का पालन करते है 2e ≥ 3f, क्योंकि प्रत्येक संख्या में कम से कम तीन संख्या-किनारे की होती है। यह यूलर के सूत्र के साथ इस असमानता के बीजगणितीय परिवर्तनों का अनुसरण करता है v – e + f = 2 कि परिमित समतलीय आलेख के लिए औसत डिग्री 6 से बिल्कुल कम होती है। उच्चतर औसत डिग्री वाले आलेख समतलीय नहीं हो सकते है।

मुद्रण आलेख

Main article: वृत्त पैकिंग प्रमेय

Error creating thumbnail:

वृत्त पैकिंग प्रमेय का उदाहरण K ⁻₅, पांच शीर्ष पर पूरा आलेख।

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

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

समतलीय आलेख घनत्व

घनत्व गुणांक D एक समतलीय आलेख या, संख्या का अनुपात होता है f – 1 इसके अधिकतम संभव मानों द्वारा परिबद्ध फलन है 2v – 5 इसके लिए एक आलेख के लिए v शीर्ष:

$D={\frac {f-1}{2v-5}}$

घनत्व पालन करता है 0 ≤ D ≤ 1, साथ D = 0 के लिए पूरी तरह से विरल समतलीय आलेख, और D = 1 पूरी तरह से सघन (अधिकतम) समतलीय आलेख के लिए होता है।

दोहरा आलेख

File:Dual graphs.svg

एक समतलीय आलेख और उसका दोहरा आलेख

एक अंतर्निहित दिया गया G किनारों के प्रतिच्छेदन के बिना समतल में (आवश्यक रूप से सरल नहीं) जुड़े हुए आलेख का, हम दोहरे आलेख का निर्माण करते है G* इस प्रकार है: हम प्रत्येक फलन में एक शीर्ष चुनते है G (बाहरी संख्या सहित) और प्रत्येक किनारे के लिए e में G हम एक नई बढ़त का परिचय देते है G* दो शीर्ष को अंदर जोड़ना G* दो संख्याओ के अनुरूप G यहां मिलते है e. इसके अतिरिक्त, यह किनारा खींचा जाता है जिससे कि यह पार हो जाता है e और उसका कोई दूसरा किनारा नहीं होता है G या G* प्रतिच्छेदित होता है. तब G* फिर से एक (आवश्यक नहीं कि सरल) समतलीय आलेख का अंतर्निहित होता है, इसके उतने ही किनारे है G, जितने शीर्ष G के संख्या और उतने ही संख्या है जितनी G शीर्ष की होती है G** = G, यहां समानता अंतर्निहित की तुल्यता होती है। यदि G तो उत्तल बहुफलन के अनुरूप समतलीय आलेख होता है G* दोहरे बहुफलन के अनुरूप समतलीय आलेख होता है।

यह दोहरे उपयोगी होते है क्योंकि दोहरे आलेख के कई गुण मूल आलेख के गुणों से सरल विधियों से संबंधित होते है, जिससे उनके दोहरे आलेख की जांच करके आलेख के बारे में परिणामों को सिद्ध किया जा सकता है।

जबकि किसी विशेष अंतर्निहित के लिए निर्मित दोहरा अद्वितीय होता है (समाकृतिकता तक), आलेख में अलग-अलग (अर्थात गैर-समरूपी) दोहरा हो सकते है, जो अलग-अलग (अर्थात समरूपी) अंतर्निहित से प्राप्त होते है।

तलीय रेखांकन के वर्ग

अधिकतम समतलीय आलेख

File:Goldner-Harary graph.svg

गोल्डनर-हैरी आलेख अधिकतम समतलीय है। इसके सभी मुख तीन किनारों से घिरे हुए है।

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

यदि एक अधिकतम समतलीय आलेख है v शीर्ष के साथ v > 2, तो यह बिल्कुल ठीक है 3v – 6 किनारे और 2v – 4।

अपोलोनियन संजाल त्रिकोणीय को बार-बार छोटे त्रिकोणों के त्रिगुणों में विभाजित करके बनाए गए अधिकतम समतलीय आलेख होता है। सामान्यतः, वे समतलीय k-ट्री होते है।

स्ट्रेंग्युलेटेड आलेख वे आलेख होते है जिनमें प्रत्येक परिधीय चक्र एक त्रिभुज होता है। अधिकतम समतलीय आलेख (या अधिक सामान्यतः एक बहुफलनीय आलेख) में परिधीय चक्र फलन होते है। इस आलेख में कॉर्डल आलेख भी सम्मलित होते है, और ये बिल्कुल ऐसे आलेख होते है जो पूर्ण आलेख और अधिकतम योजना आलेख के योग किनारों को हटाए बिना बनाए जा सकते है।

आउटरयोजना आलेख

आउटरयोजना आलेख समतल में अंतर्निहित वाले आलेख होते है, जैसे कि सभी कोने अंतर्निहित के असीमित संख्या से संबंधित होते है। प्रत्येक बाहरी तलीय आलेख समतलीय होते है, लेकिन इसका विपरीत सत्य नहीं है: K₄ समतलीय है लेकिन बाह्यतलीय नहीं है। कुराटोस्की के समान एक प्रमेय में कहा गया है कि एक परिमित आलेख बाहरी तलीय होता है यदि और केवल तभी जब इसमें उपविभाजन न हो K₄ या का K_2,3. उपरोक्त इस तथ्य का प्रत्यक्ष परिणाम है कि एक आलेख {{mvar|G}यदि आलेख से बना है तो } आउटरयोजना है G एक नया शीर्ष जोड़कर, किनारों के साथ इसे अन्य सभी शीर्ष से जोड़कर, एक समतल आलेख बनता है।

आलेख का 1-आउटरयोजना अंतर्निहित आउटरयोजना अंतर्निहित के समान होता है। इसके लिए k > 1 एक समतल अंतर्निहित होता है k-आउटरयोजना यदि बाहरी फलन पर शीर्ष को हटाने पर परिणाम मिलता है (k – 1)।

हैलिन आलेख

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

समतलीय आलेख

एक उर्ध्व तलीय आलेख एक निर्देशित चक्रीय आलेख होता है जिसे समतल में इसके किनारों के साथ गैर-क्रॉसिंग वक्र के रूप में खींचा जा सकता है जो लगातार ऊपर की दिशा में उन्मुख होते है। प्रत्येक तलीय निर्देशित अचक्रीय आलेख उर्ध्व तलीय नहीं होता है, और यह परीक्षण करने के लिए एनपी-पूर्ण है कि कोई दिया गया आलेख उर्ध्व तलीय है या नहीं है।

उत्तल तलीय आलेख

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

शब्द-प्रतिनिधित्व योग्य समतलीय आलेख

शब्द-प्रतिनिधित्व योग्य समतलीय आलेख में त्रिभुज-मुक्त समतलीय आलेख और, अधिक सामान्यतः, 3-रंगीय समतलीय आलेख सम्मलित होते है।

प्रमेय

समतलीय आलेख की गणना

समतल आलेख की संख्या के लिए स्पर्शोन्मुख विश्लेषण $n$ शीर्ष है $g\cdot n^{-7/2}\cdot \gamma ^{n}\cdot n!$, जहाँ $\gamma \approx 27.22687$ और $g\approx 0.43\times 10^{-5}$.

लगभग सभी समतलीय आलेखों में ऑटोमोर्फिज्म की घातीय संख्या होती है।

गैर-समरूपी समतल आलेख की संख्या $n$ शीर्ष के बीच है $27.2^{n}$ और $30.06^{n}$.

अन्य परिणाम

चार रंग प्रमेय में कहा गया है कि प्रत्येक समतलीय आलेख आलेख रंग (अर्थात, 4-बिंदु) होते है।

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

शीनरमैन का प्रमेय बताता है कि प्रत्येक समतल आलेख को समतल में रेखा वर्गों के प्रतिच्छेदन आलेख के रूप में दर्शाया जा सकता है।

समतल विभाजक प्रमेय में कहा गया है कि प्रत्येक एन-शीर्ष समतल आलेख को आलेख सिद्धांत की दो वाक्यांश में विभाजित किया जा सकता है O को हटाकर अधिकतम 2n/3 आकार के उपआलेख√n) शीर्ष. परिणामस्वरूप, समतलीय आलेख में ट्री-चौड़ाई होती है O(√n).

समतलीय उत्पाद संरचना प्रमेय में कहा गया है कि प्रत्येक समतलीय आलेख अधिकतम 8 और एक पथ पर ट्री चौड़ाई वाले आलेख के मजबूत आलेख उत्पाद का एक उपआलेख होता है।

इस परिणाम का उपयोग यह दिखाने के लिए किया जाता है कि समतल आलेख में परिबद्ध संख्या, रंगीन संख्या और निकट-रेखीय आकार के सार्वभौमिक आलेख होते है। इसमें शीर्ष वर्गों के लिए भी उपकरण होते है पी-केंद्रित रंग समतलीय रेखांकन का V शीर्ष वाले दो समतलीय आलेखों के लिए, O(v) में यह निर्धारित करना संभव होता है कि वह आलेख सिद्धांत है या नहीं है (आलेख समरूपता समस्या भी देखें)।

सामान्यीकरण

शीर्ष आलेख एक ऐसा आलेख होता है जिसे एक शीर्ष को हटाकर समतल बनाया जा सकता है, और के-एपेक्स आलेख एक ऐसा आलेख होता है जिसे अधिकतम k शीर्ष को हटाकर समतल बनाया जा सकता है।

1-तलीय आलेख एक ऐसा आलेख होता है जिसे प्रति किनारे अधिकतम एक साधारण क्रॉसिंग के साथ समतल में खींचा जा सकता है, और के-योजना आलेख एक ऐसा आलेख होता है जिसे प्रति किनारे अधिकतम एक साधारण क्रॉसिंग के साथ खींचा जा सकता है।

मानचित्र आलेख एक ऐसा आलेख होता है जो दो क्षेत्रों को जोड़कर समतल में बहुत सारे सरलता से जुड़े हुए आंतरिक-विच्छेदित क्षेत्रों के एक समूह से बनता है। जब अधिकतम तीन क्षेत्र एक बिंदु पर मिलते है, तो परिणाम एक समतलीय आलेख होता है, लेकिन जब चार या अधिक क्षेत्र एक बिंदु पर मिलते है, तो परिणाम गैर-तलीय हो सकता है।

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

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

यह भी देखें

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

संदर्भ

• Kuratowski, Kazimierz (1930), "Sur le problème des courbes gauches en topologie" (PDF), Fundamenta Mathematicae (in français), 15: 271–283, doi:10.4064/fm-15-1-271-283.
• Wagner, K. (1937), "Über eine Eigenschaft der ebenen Komplexe", Mathematische Annalen (in Deutsch), 114: 570–590, doi:10.1007/BF01594196, S2CID 123534907.
• Boyer, John M.; Myrvold, Wendy J. (2005), "On the cutting edge: Simplified O(n) planarity by edge addition" (PDF), Journal of Graph Algorithms and Applications, 8 (3): 241–273, doi:10.7155/jgaa.00091.
• McKay, Brendan; Brinkmann, Gunnar, A useful planar graph generator.
• de Fraysseix, H.; Ossona de Mendez, P.; Rosenstiehl, P. (2006), "Trémaux trees and planarity", International Journal of Foundations of Computer Science, 17 (5): 1017–1029, arXiv:math/0610935, doi:10.1142/S0129054106004248, S2CID 40107560. Special Issue on Graph Drawing.
• Bader, D.A.; Sreshta, S. (October 1, 2003). A New Parallel Algorithm for Planarity Testing (Technical report). UNM-ECE Technical Report 03-002. Archived from the original on 2016-03-16.
• 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.

बाहरी संबंध

• Edge Addition Planarity Algorithm Source Code, version 1.0 — Free C source code for reference implementation of Boyer–Myrvold planarity algorithm, which provides both a combinatorial planar embedder and Kuratowski subgraph isolator. An open source project with free licensing provides the Edge Addition Planarity Algorithms, current version.
• Public Implementation of a Graph Algorithm Library and Editor — GPL graph algorithm library including planarity testing, planarity embedder and Kuratowski subgraph exhibition in linear time.
• Boost Graph Library tools for planar graphs, including linear time planarity testing, embedding, Kuratowski subgraph isolation, and straight-line drawing.
• 3 Utilities Puzzle and Planar Graphs
• NetLogo Planarity model — NetLogo version of John Tantalo's game