बहुभुज-वृत्त ग्राफ
रेखांकन सिद्धांत के गणित अनुशासन में, बहुभुज-वृत्त रेखांकन उत्तल बहुभुज के समूह का प्रतिच्छेदन रेखांकन है | जिसके सभी शीर्ष (ज्यामिति) सामान्य वृत्त पर स्थित हैं। इन रेखांकन को तंतु रेखांकन भी कहा जाता है। रेखांकन के इस वर्ग को पहली बार 1988 में माइकल फेलो द्वारा सुझाया गया था | इस तथ्य से प्रेरित होकर कि यह किनारे के संकुचन और प्रेरित सबरेखांकन संचालन के अनुसार बंद है।[1]
बहुभुज-वृत्त रेखांकन को वैकल्पिक क्रम के रूप में दर्शाया जा सकता है। इस तरह के अनुक्रम को रेखांकन (यदि आवश्यक हो) का प्रतिनिधित्व करने वाले बहुभुजों को हानि पहुचा कर प्राप्त किया जा सकता है | जिससे कोई दो शीर्ष साझा न करें, और उसके बाद प्रत्येक शीर्ष के लिए सूचीबद्ध करें (परिपत्र क्रम में,इच्छानुसार बिंदु से प्रारंभ) बहुभुज उस शीर्ष से जुड़ा हुआ है।
उत्प्रेरित अवयस्कों के अंतर्गत बंद
बहुभुज-वृत्त रेखांकन के किनारों के सिकुड़ने से एक और बहुभुज-वृत्त रेखांकन बनता है। नए रेखांकन का ज्यामितीय प्रतिनिधित्व उनके उत्तल पतवार द्वारा अनुबंधित किनारे के दो समापन बिंदुओं के अनुरूप बहुभुजों को बदलकर बनाया जा सकता है। वैकल्पिक रूप से, मूल रेखांकन का प्रतिनिधित्व करने वाले वैकल्पिक अनुक्रम में, अनुबंधित किनारे के समापन बिंदुओं को एकल अनुक्रम में दर्शाने वाले अनुक्रमों को जोड़कर अनुबंधित रेखांकन के वैकल्पिक अनुक्रम प्रतिनिधित्व का उत्पादन होता है। बहुभुज-वृत्त रेखांकन भी प्रेरित सबरेखांकन या समकक्ष शीर्ष विलोपन संचालन के अनुसार बंद होते हैं: | शीर्ष को हटाने के लिए, इसके बहुभुज को ज्यामितीय प्रतिनिधित्व से हटा दें, या वैकल्पिक क्रम से इसके बिंदुओं को हटा देते है |
पहचान
एम. कोएबे ने बहुपद समय पहचान एल्गोरिदम की घोषणा की थी |,[2] चूँकि उनके प्रारंभिक संस्करण में गंभीर त्रुटियाँ थीं |[3] और अंतिम संस्करण कभी प्रकाशित नहीं हुआ था। [1] मार्टिन पर्गेल ने बाद में सिद्ध किया कि इन रेखांकनों को पहचानने की समस्या एनपी-पूर्ण है।[4] यह निर्धारित करने के लिए एनपी-पूर्ण भी है कि किसी दिए गए रेखांकन को बहुभुज-वृत्त रेखांकन के रूप में अधिक से अधिक प्रदर्शित किया जा सकता है | जिसमे किसी भी k ≥ 3 के लिए प्रति बहुभुज अधिकतम k शीर्ष होते है |[1]
संबंधित रेखांकन समूह
बहुभुज-वृत्त रेखांकन वृत्त रेखांकन का सामान्यीकरण है,| जो वृत्त के जीवाओं के प्रतिच्छेदन रेखांकन हैं, और चतुर्भुज रेखांकन, चतुर्भुज के प्रतिच्छेदन के रेखांकन हैं | जो सभी समान दो समानांतर रेखाओं पर उनके कोने हैं। इनमें गोलाकार चाप रेखांकन भी सम्मिलित हैं। [1][5]
बहुभुज-वृत्त रेखांकन, सामान्यतः, पूर्ण रेखांकन नहीं होते हैं | किन्तु वे निकट-परिपूर्ण होते हैं, इस अर्थ में कि उनके रंगीन नंबरों को उनके गुट संख्या के (घातीय) फलन द्वारा बाध्य किया जा सकता है।[6]
संदर्भ
- ↑ 1.0 1.1 1.2 1.3 Kratochvíl, Jan; Pergel, Martin (2004), "Two results on intersection graphs of polygons", Graph Drawing: 11th International Symposium, GD 2003 Perugia, Italy, September 21-24, 2003, Revised Papers, Lecture Notes in Computer Science, vol. 2912, Berlin: Springer, pp. 59–70, doi:10.1007/978-3-540-24595-7_6, MR 2177583.
- ↑ Koebe, Manfred (1992), "On a new class of intersection graphs", Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity (Prachatice, 1990), Ann. Discrete Math., vol. 51, North-Holland, Amsterdam, pp. 141–143, doi:10.1016/S0167-5060(08)70618-6, MR 1206256.
- ↑ Spinrad, Jeremy P. (2003), Efficient graph representations, Fields Institute Monographs, vol. 19, American Mathematical Society, Providence, RI, p. 41, ISBN 0-8218-2815-0, MR 1971502.
- ↑ Pergel, Martin (2007), "Recognition of polygon-circle graphs and graphs of interval filaments is NP-complete", Graph-Theoretic Concepts in Computer Science: 33rd International Workshop, WG 2007, Dornburg, Germany, June 21-23, 2007, Revised Papers, Lecture Notes in Computer Science, vol. 4769, Berlin: Springer, pp. 238–247, doi:10.1007/978-3-540-74839-7_23, MR 2428581.
- ↑ Spider graphs, Information System on Graph Classes and their Inclusions, retrieved 2016-07-11.
- ↑ Kostochka, Alexandr; Kratochvíl, Jan (1997), "Covering and coloring polygon-circle graphs", Discrete Mathematics, 163 (1–3): 299–305, doi:10.1016/S0012-365X(96)00344-5, MR 1428585.
