क्रॉसिंग नंबर (ग्राफ़ सिद्धांत)

तीन क्रॉसिंग के साथ हेवुड ग्राफ का एक चित्र। यह इस ग्राफ़ के सभी रेखाचित्रों में क्रॉसिंग की न्यूनतम संख्या है, इसलिए ग्राफ़ में क्रॉसिंग संख्या

cr(G) = 3

है।

ग्राफ़ सिद्धांत में, ग्राफ़ $G$ की क्रॉसिंग संख्या $cr(G)$ ग्राफ़ $G$ के समतल आरेखण के किनारे क्रॉसिंग की सबसे कम संख्या है। उदाहरण के लिए, एक ग्राफ़ समतल है यदि और केवल यदि इसकी क्रॉसिंग संख्या शून्य है। ग्राफ़ ड्राइंग में क्रॉसिंग संख्या का निर्धारण बहुत महत्वपूर्ण है, क्योंकि उपयोगकर्ता अध्ययनों से पता चला है कि कुछ क्रॉसिंग के साथ ग्राफ़ खींचने से लोगों के लिए ड्राइंग को समझना आसान हो जाता है।^[1]

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

क्रॉसिंग संख्या असमानता बताती है कि, ऐसे ग्राफ़ के लिए जहां किनारों की संख्या ई शीर्षों की संख्या $n$ से पर्याप्त रूप से बड़ी है, क्रॉसिंग संख्या कम से कम $e 3 / n 2$ के समानुपाती होती है। इसमें वीएलएसआई डिज़ाइन और घटना ज्यामिति में अनुप्रयोग हैं।

आगे की योग्यता के बिना क्रॉसिंग संख्या उन चित्रों की अनुमति देती है जिनमें किनारों को इच्छानुसार वक्रों द्वारा दर्शाया जा सकता है। इस अवधारणा का एक रूपांतर, रेक्टिलिनियर क्रॉसिंग नंबर, के लिए सभी किनारों को सीधी रेखा खंड होना आवश्यक है, और क्रॉसिंग नंबर से भिन्न हो सकता है। विशेष रूप से, एक पूर्ण ग्राफ़ की सीधी रेखा क्रॉसिंग संख्या अनिवार्य रूप से सामान्य स्थिति में $n$ बिंदुओं के एक सेट द्वारा निर्धारित उत्तल चतुर्भुजों की न्यूनतम संख्या के समान होती है। इस संख्या को निर्धारित करने की समस्या का सुखद अंत की समस्या से गहरा संबंध है।^[4]

परिभाषाएँ

क्रॉसिंग संख्या को परिभाषित करने के प्रयोजनों के लिए, एक अप्रत्यक्ष ग्राफ का चित्रण ग्राफ़ के शीर्षों से लेकर समतल में असंयुक्त बिंदुओं तक और ग्राफ़ के किनारों से लेकर उनके दो अंतिम बिंदुओं को जोड़ने वाले वक्रों तक का मानचित्रण है। किसी भी शीर्ष को उस किनारे पर मैप नहीं किया जाना चाहिए जिसका वह समापन बिंदु नहीं है, और जब भी दो किनारों पर वक्र होते हैं जो प्रतिच्छेद करते हैं (एक साझा समापन बिंदु के अतिरिक्त) तो उनके प्रतिच्छेदन को उचित क्रॉसिंग का एक सीमित सेट बनाना चाहिए, जहां दो वक्र ट्रांसवर्सलिटी हैं ( अंक शास्त्र)। इनमें से प्रत्येक क्रॉसिंग बिंदु के लिए, क्रॉस करने वाले किनारों के प्रत्येक जोड़े के लिए एक क्रॉसिंग को अलग से गिना जाता है। किसी ग्राफ़ की क्रॉसिंग संख्या, ऐसे सभी रेखाचित्रों पर, किसी ड्राइंग में क्रॉसिंग की संख्या की न्यूनतम होती है।^[5]

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

विशेष स्थिति

अप्रैल 2015 तक बहुत कम ग्राफ़ वर्गों के लिए क्रॉसिंग नंबर ज्ञात हैं। विशेष रूप से, कुछ प्रारंभिक स्थितियों को छोड़कर, पूर्ण ग्राफ़ की क्रॉसिंग संख्या, द्विदलीय पूर्ण ग्राफ़ और चक्रों के उत्पाद सभी अज्ञात रहते हैं, चूँकि निचली सीमाओं पर कुछ प्रगति हुई है।^[6]

पूर्ण द्विदलीय ग्राफ

का एक इष्टतम चित्रण

K 4,7

दिखा रहा है कि 4 संचयन स्थलों (पीले धब्बे) और 7 भट्टियों (नीले धब्बे) के साथ तुरान की ईंट फैक्ट्री की समस्या के लिए 18 क्रॉसिंग (लाल बिंदु) की आवश्यकता है

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

एक पूर्ण द्विदलीय ग्राफ के रेखांकन में क्रॉसिंग की न्यूनतम संभव संख्या क्या है?^[7]

काज़िमिर्ज़ ज़ारांकिविज़ ने तुरान की ईंट फैक्ट्री की समस्या को हल करने का प्रयास किया;^[8] उनके प्रमाण में एक त्रुटि थी, किन्तु उन्होंने एक वैध ऊपरी और निचली सीमा स्थापित की थी

{\textrm {cr}}(K_{m,n})\leq \left\lfloor {\frac {n}{2}}\right\rfloor \left\lfloor {\frac {n-1}{2}}\right\rfloor \left\lfloor {\frac {m}{2}}\right\rfloor \left\lfloor {\frac {m-1}{2}}\right\rfloor

संपूर्ण द्विदलीय ग्राफ की क्रॉसिंग संख्या के लिए $K m,n$ . इस सीमा को सभी पूर्ण द्विदलीय ग्राफ़ के लिए क्रॉसिंग की इष्टतम संख्या होने का अनुमान लगाया गया है।^[9]

पूर्ण ग्राफ़ और ग्राफ़ रंग

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

{\textrm {cr}}(K_{p})\leq {\frac {1}{4}}\left\lfloor {\frac {p}{2}}\right\rfloor \left\lfloor {\frac {p-1}{2}}\right\rfloor \left\lfloor {\frac {p-2}{2}}\right\rfloor \left\lfloor {\frac {p-3}{2}}\right\rfloor

क्रॉसिंग. यह सूत्र $p = 5, ..., 12$ के लिए $1, 3, 9, 18, 36, 60, 100, 150$ का मान देता है; पूर्णांक अनुक्रमों के ऑन-लाइन विश्वकोश में अनुक्रम A000241 देखें। अनुमान यह है कि इससे उत्तम कोई रेखांकन नहीं हो सकता है, इसलिए यह सूत्र संपूर्ण ग्राफ़ के लिए क्रॉसिंग की इष्टतम संख्या देता है। इसी अनुमान का एक स्वतंत्र सूत्रीकरण 1964 में थॉमस एल. सैटी द्वारा किया गया था।^[11]

सैटी ने आगे सत्यापित किया कि यह सूत्र $p \leq 10$ के लिए क्रॉसिंग की इष्टतम संख्या देता है और पैन और रिक्टर ने दिखाया कि यह $p = 11, 12$ के लिए भी इष्टतम है।^[12]

2007 में माइकल ओ. अल्बर्टसन द्वारा तैयार अल्बर्टसन अनुमान में कहा गया है कि, रंगीन संख्या $n$ वाले सभी ग्राफ़ों के बीच, पूर्ण ग्राफ़ $K n$ में क्रॉसिंग की न्यूनतम संख्या होती है। अर्थात्, यदि पूर्ण ग्राफ़ की क्रॉसिंग संख्या के लिए अनुमानित सूत्र सही है, तो प्रत्येक $n$ -क्रोमैटिक ग्राफ़ में कम से कम उसी सूत्र के समान क्रॉसिंग संख्या होती है। अल्बर्टसन अनुमान अब $n \leq 16$ के लिए मान्य माना जाता है।^[13]

घन ग्राफ

क्रॉसिंग नंबर 1-8 और 11 वाले सबसे छोटे क्यूबिक ग्राफ़ ज्ञात हैं ((sequence A110507 in the OEIS) सबसे छोटा 1-क्रॉसिंग क्यूबिक ग्राफ 6 शीर्षों के साथ पूर्ण द्विदलीय ग्राफ $K 3,3$ है। सबसे छोटा 2-क्रॉसिंग क्यूबिक ग्राफ़ पीटरसन ग्राफ है, जिसमें 10 शीर्ष हैं। सबसे छोटा 3-क्रॉसिंग क्यूबिक ग्राफ हेवुड ग्राफ है, जिसमें 14 शीर्ष हैं। सबसे छोटा 4-क्रॉसिंग क्यूबिक ग्राफ़ मोबियस-कांटोर ग्राफ़ है, जिसमें 16 शीर्ष हैं। सबसे छोटा 5-क्रॉसिंग क्यूबिक ग्राफ पप्पस ग्राफ है, जिसमें 18 शीर्ष हैं। सबसे छोटा 6-क्रॉसिंग क्यूबिक ग्राफ़ डेसर्गेस ग्राफ है, जिसमें 20 शीर्ष हैं। 22 शीर्षों वाले चार 7-क्रॉसिंग क्यूबिक ग्राफ़ों में से कोई भी प्रसिद्ध नहीं है।^[14] सबसे छोटे 8-क्रॉसिंग क्यूबिक ग्राफ़ में 24 शीर्षों के साथ नाउरू ग्राफ और मैक्गी ग्राफ या (3,7)- पिंजरे का ग्राफ सम्मिलित हैं।^[15] सबसे छोटे 11-क्रॉसिंग क्यूबिक ग्राफ़ में 28 शीर्षों वाला कॉक्सेटर ग्राफ सम्मिलित है।^[16]

2009 में, पेग और एक्सू ने अनुमान लगाया कि क्रॉसिंग नंबर 13 के साथ सबसे छोटा क्यूबिक ग्राफ टुटे-कॉक्सेटर ग्राफ है और क्रॉसिंग नंबर 170 के साथ सबसे छोटा क्यूबिक ग्राफ सभी 12-पिंजरे है।^[15]^[17]

द्विभाजन चौड़ाई से कनेक्शन

एक साधारण ग्राफ $G$ की 2/3-द्विभाजन चौड़ाई $b(G)$ किनारों की न्यूनतम संख्या है जिसके हटाने के परिणामस्वरूप शीर्ष का विभाजन दो अलग-अलग सेटों में हो जाता है जिससे किसी भी सेट में $2n/3$ से अधिक कोने न हों। कंप्यूटिंग $b(G)$ एनपी-हार्ड है। लीटन ने सिद्ध किया कि $cr(G)+n=\Omega (b^{2}(G))$ , परन्तु कि $G$ ने शीर्ष डिग्री को सीमित कर दिया हो।^[18] इस मूलभूत असमानता का उपयोग $cr(G)$ के लिए एक एसिम्प्टोटिक निचली सीमा प्राप्त करने के लिए किया जा सकता है, जब $b(G)$ , या इसका एक अनुमान ज्ञात हो। इसके अलावा, इस असमानता में एल्गोरिथम अनुप्रयोग है। विशेष रूप से, भट्ट और लीटन ने इसका उपयोग (पहली बार) एक ड्राइंग में किनारे क्रॉसिंग की संख्या पर ऊपरी सीमा प्राप्त करने के लिए किया था, जो $cr(G)$ की गणना के लिए एक विभाजन और जीत सन्निकटन एल्गोरिथ्म द्वारा प्राप्त किया जाता है।^[19]

जटिलता और सन्निकटन

सामान्यतः किसी ग्राफ़ की क्रॉसिंग संख्या निर्धारित करना कठिन होता है; माइकल गैरी और डेविड एस. जॉनसन ने 1983 में दिखाया कि यह एक एनपी कठिन समस्या है।^[20] वास्तव में क्यूबिक ग्राफ़ तक सीमित होने पर भी समस्या एनपी-हार्ड बनी रहती है^[21] और इन-प्लानर ग्राफ़ (ग्राफ़ जो एक किनारे को हटाने के बाद समतल हो जाता है)।^[22] एक निकट से संबंधित समस्या, रेक्टिलिनियर क्रॉसिंग संख्या का निर्धारण, वास्तविकताओं के अस्तित्व संबंधी सिद्धांत के लिए पूर्ण (जटिलता) है।^[23]

सकारात्मक पक्ष पर, यह निर्धारित करने के लिए कुशल एल्गोरिदम हैं कि क्या क्रॉसिंग संख्या एक निश्चित स्थिरांक $k$ से कम है। दूसरे शब्दों में, समस्या निश्चित-पैरामीटर पर सुव्यवस्थित है।^[24]^[25] बड़े $k$ के लिए यह कठिन रहता है, जैसे कि $k = | V |/2$ . परिबद्ध डिग्री^[26] के ग्राफ़ पर $cr(G)+n$ का अनुमान लगाने के लिए कुशल सन्निकटन एल्गोरिदम भी हैं जो भट्ट और लीटन के सामान्य और पहले से विकसित ढांचे का उपयोग करते हैं।^[19] वास्तव में अनुमानी एल्गोरिदम का उपयोग किया जाता है, जैसे कि सरल एल्गोरिदम जो बिना किसी किनारे के प्रारंभ होता है और निरंतर प्रत्येक नए किनारे को इस तरह से जोड़ता है जिससे कम से कम अतिरिक्त क्रॉसिंग संभव हो। इन एल्गोरिदम का उपयोग रेक्टिलिनियर क्रॉसिंग नंबर वितरित कंप्यूटिंग प्रोजेक्ट में किया जाता है।^[27]

क्रॉसिंग संख्या असमानता

एक अप्रत्यक्ष सरल ग्राफ के लिए $G$ साथ $n$ शीर्ष और $e$ किनारे ऐसे कि $e > 7 n$ क्रॉसिंग नंबर सदैव कम से कम होता है

\operatorname {cr} (G)\geq {\frac {e^{3}}{29n^{2}}}.

किनारों, शीर्षों और क्रॉसिंग संख्या के बीच इस संबंध की खोज स्वतंत्र रूप से मिक्लोस अजताई, वैक्लाव च्वाटल|च्वाटल, न्यूबॉर्न और एंड्रे ज़ेमेरेडी|सेमेरेडी द्वारा की गई थी।^[28] और लीटन द्वारा।^[18] इसे क्रॉसिंग संख्या असमानता या क्रॉसिंग लेम्मा के रूप में जाना जाता है।

स्थिरांक 29 अब तक ज्ञात सबसे अच्छा है और एकरमैन के कारण है।^[29] स्थिरांक 7 को 4 तक कम किया जा सकता है किन्तु 29 को 64 के सबसे खराब स्थिरांक से बदलने की कीमत पर।^[28]^[18]

क्रॉसिंग नंबरों का अध्ययन करने में लीटन की प्रेरणा सैद्धांतिक कंप्यूटर विज्ञान में वीएलएसआई डिजाइन के अनुप्रयोगों के लिए थी।^[18] बाद में, शेकली को यह भी एहसास हुआ कि इस असमानता से घटना (ज्यामिति) में कुछ महत्वपूर्ण प्रमेयों के बहुत ही सरल प्रमाण मिले हैं, जैसे बेक का प्रमेय (ज्यामिति)|बेक का प्रमेय और ज़ेमेरेडी-ट्रॉटर प्रमेय,^[30] और तमाल दिवस ने इसका उपयोग K-सेट (ज्यामिति) या ज्यामितीय k-सेट पर ऊपरी सीमा सिद्ध करने के लिए किया।^[31]

भिन्नताएँ

यदि किनारों को मनमाने वक्रों के बजाय सीधी रेखा खंडों के रूप में खींचने की आवश्यकता है, तो कुछ ग्राफ़ को अधिक क्रॉसिंग की आवश्यकता होती है। रेक्टिलिनियर क्रॉसिंग नंबर को इस प्रकार की ड्राइंग में क्रॉसिंग की न्यूनतम संख्या के रूप में परिभाषित किया गया है। यह हमेशा कम से कम क्रॉसिंग संख्या जितना बड़ा होता है, और कुछ ग्राफ़ के लिए बड़ा होता है। यह ज्ञात है कि, सामान्य तौर पर, रेक्टिलिनियर क्रॉसिंग नंबर को क्रॉसिंग नंबर के किसी फ़ंक्शन द्वारा सीमित नहीं किया जा सकता है। [32] $K 5$ से $K 12$ तक की सीधी क्रॉसिंग संख्याएं $1, 3, 9, 19, 36, 62, 102, 153$ (A014540) हैं और $K 27$ तक के मान ज्ञात हैं, $K 28$ के लिए 7233 या 7234 क्रॉसिंग की आवश्यकता होती है। आगे के मान रेक्टिलिनियर क्रॉसिंग नंबर प्रोजेक्ट द्वारा एकत्र किए जाते हैं।^[27]

एक ग्राफ़ में स्थानीय क्रॉसिंग संख्या $k$ होती है यदि इसे प्रति किनारे अधिकतम $k$ क्रॉसिंग के साथ खींचा जा सकता है, किन्तु कम नहीं वे ग्राफ़ जिन्हें प्रति किनारे अधिकतम k क्रॉसिंग के साथ खींचा जा सकता है, उन्हें $k$ -प्लानर भी कहा जाता है।^[32]

क्रॉसिंग नंबर के अन्य प्रकारों में जोड़ीदार क्रॉसिंग नंबर (किसी भी ड्राइंग में किनारों के जोड़े की न्यूनतम संख्या जो क्रॉस करते हैं) और विषम क्रॉसिंग नंबर (किनारों के जोड़े की संख्या जो किसी भी ड्राइंग में विषम संख्या में क्रॉस करते हैं) सम्मिलित हैं। विषम क्रॉसिंग संख्या अधिक से अधिक जोड़ीवार क्रॉसिंग संख्या के समान होती है, जो अधिक से अधिक क्रॉसिंग संख्या के समान होती है। चूँकि , हनानी-टुटे प्रमेय के अनुसार, जब भी इनमें से एक संख्या शून्य होती है, तो वे सभी शून्य होती हैं।^[5] Schaefer (2014, 2018) ऐसे कई वेरिएंट का सर्वेक्षण करता है।^[33]^[34]

यह भी देखें

समतलीकरण एक समतलीय ग्राफ है जो प्रत्येक क्रॉसिंग को एक नए शीर्ष द्वारा प्रतिस्थापित करके बनाया जाता है
तीन उपयोगिताओं की समस्या, पहेली जो पूछती है कि क्या $K 3,3$ को 0 क्रॉसिंग के साथ खींचा जा सकता है

संदर्भ

↑ Purchase, Helen C.; Cohen, Robert F.; James, Murray I. (1995). "Validating graph drawing aesthetics". In Brandenburg, Franz-Josef (ed.). Graph Drawing, Symposium on Graph Drawing, GD '95, Passau, Germany, September 20-22, 1995, Proceedings. Lecture Notes in Computer Science. Vol. 1027. Springer. pp. 435–446. doi:10.1007/BFb0021827..
↑ Turán, P. (1977). "A Note of Welcome". Journal of Graph Theory. 1: 7–9. doi:10.1002/jgt.3190010105.
↑ Bronfenbrenner, Urie (1944). "The graphic presentation of sociometric data". Sociometry. 7 (3): 283–289. doi:10.2307/2785096. JSTOR 2785096. The arrangement of subjects on the diagram, while haphazard in part, is determined largely by trial and error with the aim of minimizing the number of intersecting lines.
↑ Scheinerman, Edward R.; Wilf, Herbert S. (1994). "The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability". American Mathematical Monthly. 101 (10): 939–943. doi:10.2307/2975158. JSTOR 2975158.
↑ ^5.0 ^5.1 ^5.2 Pach, J.; Tóth, G. (1998). "Which crossing number is it, anyway?". Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS 1998). pp. 617–626. doi:10.1109/SFCS.1998.743512..
↑ de Klerk, E.; Maharry, J.; Pasechnik, D. V.; Richter, B.; Salazar, G. (2006). "Improved bounds for the crossing numbers of K_m,n and K_n". SIAM Journal on Discrete Mathematics. 20 (1): 189–202. arXiv:math/0404142. doi:10.1137/S0895480104442741. S2CID 1509054.
↑ Pach, János; Sharir, Micha (2009). "5.1 Crossings—the Brick Factory Problem". Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures. Mathematical Surveys and Monographs. Vol. 152. American Mathematical Society. pp. 126–127.
↑ Zarankiewicz, K. (1954). "On a Problem of P. Turán Concerning Graphs". Fundamenta Mathematicae. 41: 137–145. doi:10.4064/fm-41-1-137-145.
↑ Guy, Richard K. (1969). "The decline and fall of Zarankiewicz's theorem". Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968). Academic Press, New York. pp. 63–69. MR 0253931..
↑ ^10.0 ^10.1 Guy, R. K. (1960). "A combinatorial problem". Nabla (Bulletin of the Malayan Mathematical Society). 7: 68–72.
↑ Saaty, T.L. (1964). "The minimum number of intersections in complete graphs". Proceedings of the National Academy of Sciences of the United States of America. 52 (3): 688–690. Bibcode:1964PNAS...52..688S. doi:10.1073/pnas.52.3.688. PMC 300329. PMID 16591215.
↑ Pan, Shengjun; Richter, R. Bruce (2007). "The crossing number of $K 11$ is $100$ ". Journal of Graph Theory. 56 (2): 128–134. doi:10.1002/jgt.20249. MR 2350621. S2CID 37155969..
↑ Barát, János; Tóth, Géza (2009). "Towards the Albertson Conjecture". arXiv:0909.0413 [math.CO].
↑ Weisstein, Eric W. "Graph Crossing Number". MathWorld.
↑ ^15.0 ^15.1 Pegg, E. T.; Exoo, G. (2009). "Crossing Number Graphs". Mathematica Journal. 11 (2). doi:10.3888/tmj.11.2-2.
↑ Clancy, Kieran; Haythorpe, Michael; Newcombe, Alex; Pegg, Ed Jr. (2020). "There are no cubic graphs on 26 vertices with crossing number 10 or 11". Graphs and Combinatorics. 36 (6): 1713–1721. arXiv:1804.10336. doi:10.1007/s00373-020-02204-6. MR 4163409.
↑ Exoo, G. "Rectilinear Drawings of Famous Graphs".
↑ ^18.0 ^18.1 ^18.2 ^18.3 Leighton, T. (1983). Complexity Issues in VLSI. Foundations of Computing Series. Cambridge, MA: MIT Press.
↑ ^19.0 ^19.1 Bhatt, Sandeep N.; Leighton, Frank Thomson (1984-04-01). "A framework for solving VLSI graph layout problems". Journal of Computer and System Sciences (in English). 28 (2): 300–343. doi:10.1016/0022-0000(84)90071-0. ISSN 0022-0000.
↑ Garey, M. R.; Johnson, D. S. (1983). "Crossing number is NP-complete". SIAM Journal on Algebraic and Discrete Methods. 4 (3): 312–316. doi:10.1137/0604033. MR 0711340.
↑ Hliněný, P. (2006). "Crossing number is hard for cubic graphs". Journal of Combinatorial Theory. Series B. 96 (4): 455–471. doi:10.1016/j.jctb.2005.09.009. MR 2232384.
↑ Cabello S. and Mohar B. (2013). "Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard". SIAM Journal on Computing. 42 (5): 1803–1829. arXiv:1203.5944. doi:10.1137/120872310. S2CID 6535755.
↑ Schaefer, Marcus (2010). Complexity of some geometric and topological problems (PDF). Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, September 2009, Revised Papers. Lecture Notes in Computer Science. Vol. 5849. Springer-Verlag. pp. 334–344. doi:10.1007/978-3-642-11805-0_32. ISBN 978-3-642-11804-3..
↑ Grohe, M. (2005). "Computing crossing numbers in quadratic time". Journal of Computer and System Sciences. 68 (2): 285–302. arXiv:cs/0009010. doi:10.1016/j.jcss.2003.07.008. MR 2059096.
↑ Kawarabayashi, Ken-ichi; Reed, Bruce (2007). Computing crossing number in linear time. Proceedings of the 29th Annual ACM Symposium on Theory of Computing. pp. 382–390. doi:10.1145/1250790.1250848. ISBN 978-1-59593-631-8.
↑ Even, Guy; Guha, Sudipto; Schieber, Baruch (2003). "Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas". SIAM Journal on Computing. 32 (1): 231–252. doi:10.1137/S0097539700373520.
↑ ^27.0 ^27.1 Oswin Aichholzer. "Rectilinear Crossing Number project". Archived from the original on 2012-12-30., and Rectilinear Crossing Number on the Institute for Software Technology at Graz, University of Technology (2009).
↑ ^28.0 ^28.1 Ajtai, M.; Chvátal, V.; Newborn, M.; Szemerédi, E. (1982). Crossing-free subgraphs. Theory and Practice of Combinatorics. North-Holland Mathematics Studies. Vol. 60. pp. 9–12. MR 0806962.
↑ Ackerman, Eyal (2013). "On topological graphs with at most four crossings per edge" (PDF). Archived from the original (PDF) on 2014-07-14.
↑ Székely, L. A. (1997). "Crossing numbers and hard Erdős problems in discrete geometry". Combinatorics, Probability and Computing. 6 (3): 353–358. doi:10.1017/S0963548397002976. MR 1464571. S2CID 36602807.
↑ Dey, T. K. (1998). "Improved bounds for planar k-sets and related problems". Discrete and Computational Geometry. 19 (3): 373–382. doi:10.1007/PL00009354. MR 1608878.
↑ Ringel, Gerhard (1965). "Ein Sechsfarbenproblem auf der Kugel". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg (in German). 29 (1–2): 107–117. doi:10.1007/BF02996313. MR 0187232. S2CID 123286264.{{cite journal}}: CS1 maint: unrecognized language (link)
↑ Schaefer, Marcus (2014). "The graph crossing number and its variants: a survey". The Electronic Journal of Combinatorics. DS21.
↑ Schaefer, Marcus (2018). Crossing Numbers of Graphs. CRC Press.

[pcj-1] Purchase, Helen C.; Cohen, Robert F.; James, Murray I. (1995). "Validating graph drawing aesthetics". In Brandenburg, Franz-Josef (ed.). Graph Drawing, Symposium on Graph Drawing, GD '95, Passau, Germany, September 20-22, 1995, Proceedings. Lecture Notes in Computer Science. Vol. 1027. Springer. pp. 435–446. doi:10.1007/BFb0021827..

[turan-2] Turán, P. (1977). "A Note of Welcome". Journal of Graph Theory. 1: 7–9. doi:10.1002/jgt.3190010105.

[bron-3] Bronfenbrenner, Urie (1944). "The graphic presentation of sociometric data". Sociometry. 7 (3): 283–289. doi:10.2307/2785096. JSTOR 2785096. The arrangement of subjects on the diagram, while haphazard in part, is determined largely by trial and error with the aim of minimizing the number of intersecting lines.

[sw-4] Scheinerman, Edward R.; Wilf, Herbert S. (1994). "The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability". American Mathematical Monthly. 101 (10): 939–943. doi:10.2307/2975158. JSTOR 2975158.

[which-5] 5.0 ^5.1 ^5.2 Pach, J.; Tóth, G. (1998). "Which crossing number is it, anyway?". Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS 1998). pp. 617–626. doi:10.1109/SFCS.1998.743512..

[kmprs-6] Klerk, E.; Maharry, J.; Pasechnik, D. V.; Richter, B.; Salazar, G. (2006). "Improved bounds for the crossing numbers of K_m,n and K_n". SIAM Journal on Discrete Mathematics. 20 (1): 189–202. arXiv:math/0404142. doi:10.1137/S0895480104442741. S2CID 1509054.

[ps-7] Pach, János; Sharir, Micha (2009). "5.1 Crossings—the Brick Factory Problem". Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures. Mathematical Surveys and Monographs. Vol. 152. American Mathematical Society. pp. 126–127.

[z-8] Zarankiewicz, K. (1954). "On a Problem of P. Turán Concerning Graphs". Fundamenta Mathematicae. 41: 137–145. doi:10.4064/fm-41-1-137-145.

[fall-9] Guy, Richard K. (1969). "The decline and fall of Zarankiewicz's theorem". Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968). Academic Press, New York. pp. 63–69. MR 0253931..

[nabla-10] 10.0 ^10.1 Guy, R. K. (1960). "A combinatorial problem". Nabla (Bulletin of the Malayan Mathematical Society). 7: 68–72.

[pnas-11] Saaty, T.L. (1964). "The minimum number of intersections in complete graphs". Proceedings of the National Academy of Sciences of the United States of America. 52 (3): 688–690. Bibcode:1964PNAS...52..688S. doi:10.1073/pnas.52.3.688. PMC 300329. PMID 16591215.

[pr-12] Pan, Shengjun; Richter, R. Bruce (2007). "The crossing number of $K 11$ is $100$ ". Journal of Graph Theory. 56 (2): 128–134. doi:10.1002/jgt.20249. MR 2350621. S2CID 37155969..

[bt-13] Barát, János; Tóth, Géza (2009). "Towards the Albertson Conjecture". arXiv:0909.0413 [math.CO].

[mathworld-14] Weisstein, Eric W. "Graph Crossing Number". MathWorld.

[pe-15] 15.0 ^15.1 Pegg, E. T.; Exoo, G. (2009). "Crossing Number Graphs". Mathematica Journal. 11 (2). doi:10.3888/tmj.11.2-2.

[hn-16] Clancy, Kieran; Haythorpe, Michael; Newcombe, Alex; Pegg, Ed Jr. (2020). "There are no cubic graphs on 26 vertices with crossing number 10 or 11". Graphs and Combinatorics. 36 (6): 1713–1721. arXiv:1804.10336. doi:10.1007/s00373-020-02204-6. MR 4163409.

[exoo-17] Exoo, G. "Rectilinear Drawings of Famous Graphs".

[leighton-18] 18.0 ^18.1 ^18.2 ^18.3 Leighton, T. (1983). Complexity Issues in VLSI. Foundations of Computing Series. Cambridge, MA: MIT Press.

[BL-19] 19.0 ^19.1 Bhatt, Sandeep N.; Leighton, Frank Thomson (1984-04-01). "A framework for solving VLSI graph layout problems". Journal of Computer and System Sciences (in English). 28 (2): 300–343. doi:10.1016/0022-0000(84)90071-0. ISSN 0022-0000.

[gj-20] Garey, M. R.; Johnson, D. S. (1983). "Crossing number is NP-complete". SIAM Journal on Algebraic and Discrete Methods. 4 (3): 312–316. doi:10.1137/0604033. MR 0711340.

[hlineny-21] Hliněný, P. (2006). "Crossing number is hard for cubic graphs". Journal of Combinatorial Theory. Series B. 96 (4): 455–471. doi:10.1016/j.jctb.2005.09.009. MR 2232384.

[cm-22] Cabello S. and Mohar B. (2013). "Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard". SIAM Journal on Computing. 42 (5): 1803–1829. arXiv:1203.5944. doi:10.1137/120872310. S2CID 6535755.

[ER-23] Schaefer, Marcus (2010). Complexity of some geometric and topological problems (PDF). Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, September 2009, Revised Papers. Lecture Notes in Computer Science. Vol. 5849. Springer-Verlag. pp. 334–344. doi:10.1007/978-3-642-11805-0_32. ISBN 978-3-642-11804-3..

[grohe-24] Grohe, M. (2005). "Computing crossing numbers in quadratic time". Journal of Computer and System Sciences. 68 (2): 285–302. arXiv:cs/0009010. doi:10.1016/j.jcss.2003.07.008. MR 2059096.

[kr-25] Kawarabayashi, Ken-ichi; Reed, Bruce (2007). Computing crossing number in linear time. Proceedings of the 29th Annual ACM Symposium on Theory of Computing. pp. 382–390. doi:10.1145/1250790.1250848. ISBN 978-1-59593-631-8.

[egs-26] Even, Guy; Guha, Sudipto; Schieber, Baruch (2003). "Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas". SIAM Journal on Computing. 32 (1): 231–252. doi:10.1137/S0097539700373520.

[rcnp-27] 27.0 ^27.1 Oswin Aichholzer. "Rectilinear Crossing Number project". Archived from the original on 2012-12-30., and Rectilinear Crossing Number on the Institute for Software Technology at Graz, University of Technology (2009).

[acns-28] 28.0 ^28.1 Ajtai, M.; Chvátal, V.; Newborn, M.; Szemerédi, E. (1982). Crossing-free subgraphs. Theory and Practice of Combinatorics. North-Holland Mathematics Studies. Vol. 60. pp. 9–12. MR 0806962.

[ackerman-29] Ackerman, Eyal (2013). "On topological graphs with at most four crossings per edge" (PDF). Archived from the original (PDF) on 2014-07-14.

[szekely-30] Székely, L. A. (1997). "Crossing numbers and hard Erdős problems in discrete geometry". Combinatorics, Probability and Computing. 6 (3): 353–358. doi:10.1017/S0963548397002976. MR 1464571. S2CID 36602807.

[dey-31] Dey, T. K. (1998). "Improved bounds for planar k-sets and related problems". Discrete and Computational Geometry. 19 (3): 373–382. doi:10.1007/PL00009354. MR 1608878.

[ringel-32] Ringel, Gerhard (1965). "Ein Sechsfarbenproblem auf der Kugel". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg (in German). 29 (1–2): 107–117. doi:10.1007/BF02996313. MR 0187232. S2CID 123286264.{{cite journal}}: CS1 maint: unrecognized language (link)

[variants-33] Schaefer, Marcus (2014). "The graph crossing number and its variants: a survey". The Electronic Journal of Combinatorics. DS21.

[book-34] Schaefer, Marcus (2018). Crossing Numbers of Graphs. CRC Press.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

Anonymous

Search

क्रॉसिंग नंबर (ग्राफ़ सिद्धांत)

Namespaces

More

Page actions

Contents

परिभाषाएँ