प्रवणता संख्या

ढलान संख्या 3 के साथ पीटरसन ग्राफ का चित्र

ग्राफ ड्राइंग और ज्यामितीय ग्राफ़ सिद्धांत में, ग्राफ़ की ढलान संख्या ग्राफ़ की ड्राइंग में किनारों के अलग-अलग ढलानों की न्यूनतम संभव संख्या होती है जिसमें कोने को यूक्लिडियन विमान में बिंदुओं के रूप में दर्शाया जाता है और किनारों को रेखा खंडों के रूप में दर्शाया जाता है। किसी भी गैर-घटना शीर्ष से न गुजरें।

पूर्ण ग्राफ़

हालाँकि असतत ज्यामिति में निकट संबंधी समस्याओं का अध्ययन पहले किया जा चुका है, उदाहरण के लिए द्वारा Scott (1970) और Jamison (1984),

ग्राफ़ की ढलान संख्या निर्धारित करने की समस्या किसके द्वारा प्रस्तुत की गई थी? Wade & Chu (1994), जिसने दिखाया कि ए की ढलान संख्या n-वर्टेक्स पूरा ग्राफ़ K_n बिलकुल हैn. ग्राफ़ के शीर्षों को नियमित बहुभुज पर रखकर इस ढलान संख्या के साथ चित्र बनाया जा सकता है।

डिग्री से संबंध

अधिकतम डिग्री के ग्राफ़ की ढलान संख्या d स्पष्ट रूप से कम से कम है $\lceil d/2\rceil$, क्योंकि घटना के अधिकतम दो किनारे डिग्री पर-d शीर्ष ढलान साझा कर सकता है। अधिक सटीक रूप से, ढलान संख्या कम से कम ग्राफ़ की रैखिक आर्बोरिसिटी के बराबर होती है, क्योंकि एकल ढलान के किनारों को रैखिक जंगल बनाना चाहिए, और बदले में रैखिक आर्बोरिसिटी कम से कम होती है $\lceil d/2\rceil$.

Unsolved problem in mathematics:

Do the graphs of maximum degree four have bounded slope number?

(more unsolved problems in mathematics)

अधिकतम डिग्री (ग्राफ सिद्धांत) पांच वाले ग्राफ़ मौजूद हैं जिनमें मनमाने ढंग से बड़ी ढलान संख्या होती है। हालाँकि, अधिकतम डिग्री तीन के प्रत्येक ग्राफ में ढलान संख्या अधिकतम चार होती है; का परिणाम Wade & Chu (1994) संपूर्ण ग्राफ़ के लिए K₄दिखाता है कि यह तंग है। चार ढलानों का प्रत्येक सेट सभी डिग्री-3 ग्राफ़ खींचने के लिए उपयुक्त नहीं है: ढलानों का सेट इस उद्देश्य के लिए उपयुक्त है यदि और केवल यदि यह समांतर चतुर्भुज के पक्षों और विकर्णों की ढलान बनाता है। विशेष रूप से, कोई भी डिग्री 3 ग्राफ़ खींचा जा सकता है ताकि उसके किनारे या तो अक्ष-समानांतर हों या पूर्णांक जाली के मुख्य विकर्णों के समानांतर हों। यह ज्ञात नहीं है कि अधिकतम डिग्री चार के ग्राफ़ में ढलान संख्या सीमित है या असीमित है।

की विधि Keszegh, Pach & Pálvölgyi (2011) परिबद्ध डिग्री के साथ समतल ग्राफ़ के लिए परिबद्ध ढलान संख्या प्राप्त करने के लिए वृत्त पैकिंग और क्वाडट्री के संयोजन के लिए

तलीय रेखांकन

जैसा Keszegh, Pach & Pálvölgyi (2011)दिखाया गया है, प्रत्येक समतलीय ग्राफ़ में फ़ेरी का प्रमेय होता है|तलीय सीधी-रेखा रेखाचित्र जिसमें अलग-अलग ढलानों की संख्या ग्राफ़ की डिग्री का कार्य है। उनका प्रमाण निर्माण का अनुसरण करता है Malitz & Papakostas (1994) समतलीय ग्राफ़ के कोणीय रिज़ॉल्यूशन (ग्राफ़ ड्राइंग) को डिग्री के फ़ंक्शन के रूप में सीमित करने के लिए, ग्राफ़ को स्थिर कारक से अधिक की डिग्री में वृद्धि किए बिना अधिकतम समतलीय ग्राफ़ में पूरा करके, और इस संवर्धित ग्राफ़ का प्रतिनिधित्व करने के लिए सर्कल पैकिंग प्रमेय को लागू करना स्पर्शरेखा वृत्तों के संग्रह के रूप में। यदि प्रारंभिक ग्राफ़ की डिग्री परिबद्ध है, तो पैकिंग में आसन्न वृत्तों की त्रिज्याओं के बीच का अनुपात भी रिंग लेम्मा द्वारा परिबद्ध होगा, जिसका तात्पर्य यह है कि प्रत्येक ग्राफ शीर्ष को उसके वृत्त के भीतर बिंदु पर रखने के लिए क्वाडट्री का उपयोग करने से ढलान उत्पन्न होंगे जो छोटे पूर्णांकों के अनुपात हैं। इस निर्माण द्वारा उत्पन्न अलग-अलग ढलानों की संख्या ग्राफ़ की डिग्री में घातीय है।

जटिलता

यह निर्धारित करना एनपी-पूर्ण है कि ग्राफ़ में ढलान संख्या दो है या नहीं। इससे यह पता चलता है कि किसी मनमाने ग्राफ की ढलान संख्या निर्धारित करना, या 3/2 से बेहतर सन्निकटन अनुपात के साथ इसका अनुमान लगाना एनपी-कठिन है।

यह निर्धारित करना भी एनपी-पूर्ण है कि क्या समतलीय ग्राफ़ में ढलान संख्या दो के साथ समतलीय रेखाचित्र है,

और वास्तविकता के अस्तित्व संबंधी सिद्धांत के लिए समतलीय रेखाचित्र की न्यूनतम ढलान संख्या निर्धारित करना कठिन है।

संदर्भ

• Barát, János; Matoušek, Jiří; Wood, David R. (2006), "Bounded-degree graphs have arbitrarily large geometric thickness", Electronic Journal of Combinatorics, 13 (1): R3, MR 2200531.
• Dujmović, Vida; Suderman, Matthew; Wood, David R. (2005), "Really straight graph drawings", in Pach, János (ed.), Graph Drawing: 12th International Symposium, GD 2004, New York, NY, USA, September 29-October 2, 2004, Revised Selected Papers, Lecture Notes in Computer Science, vol. 3383, Berlin: Springer-Verlag, pp. 122–132, arXiv:cs/0405112, doi:10.1007/978-3-540-31843-9_14.
• Eades, Peter; Hong, Seok-Hee; Poon, Sheung-Hung (2010), "On rectilinear drawing of graphs", in Eppstein, David; Gansner, Emden R. (eds.), Graph Drawing: 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers, Lecture Notes in Computer Science, vol. 5849, Berlin: Springer, pp. 232–243, doi:10.1007/978-3-642-11805-0_23, MR 2680455.
• Formann, M.; Hagerup, T.; Haralambides, J.; Kaufmann, M.; Leighton, F. T.; Symvonis, A.; Welzl, E.; Woeginger, G. (1993), "Drawing graphs in the plane with high resolution", SIAM Journal on Computing, 22 (5): 1035–1052, doi:10.1137/0222063, MR 1237161.
• Garg, Ashim; Tamassia, Roberto (2001), "On the computational complexity of upward and rectilinear planarity testing", SIAM Journal on Computing, 31 (2): 601–625, doi:10.1137/S0097539794277123, MR 1861292.
• Hansen, Lowell J. (1988), "On the Rodin and Sullivan ring lemma", Complex Variables, Theory and Application, 10 (1): 23–30, doi:10.1080/17476938808814284, MR 0946096.
• Hoffmann, Udo (2016), "The planar slope number", Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG 2016).
• Jamison, Robert E. (1984), "Planar configurations which determine few slopes", Geometriae Dedicata, 16 (1): 17–34, doi:10.1007/BF00147419, MR 0757792.
• Keszegh, Balázs; Pach, János; Pálvölgyi, Dömötör (2011), "Drawing planar graphs of bounded degree with few slopes", in Brandes, Ulrik; Cornelsen, Sabine (eds.), Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010, Revised Selected Papers, Lecture Notes in Computer Science, vol. 6502, Heidelberg: Springer, pp. 293–304, arXiv:1009.1315, doi:10.1007/978-3-642-18469-7_27, MR 2781274.
• Keszegh, Balázs; Pach, János; Pálvölgyi, Dömötör; Tóth, Géza (2008), "Drawing cubic graphs with at most five slopes", Computational Geometry: Theory and Applications, 40 (2): 138–147, doi:10.1016/j.comgeo.2007.05.003, MR 2400539.
• Malitz, Seth; Papakostas, Achilleas (1994), "On the angular resolution of planar graphs", SIAM Journal on Discrete Mathematics, 7 (2): 172–183, doi:10.1137/S0895480193242931, MR 1271989.
• Maňuch, Ján; Patterson, Murray; Poon, Sheung-Hung; Thachuk, Chris (2011), "Complexity of finding non-planar rectilinear drawings of graphs", in Brandes, Ulrik; Cornelsen, Sabine (eds.), Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010, Revised Selected Papers, Lecture Notes in Computer Science, vol. 6502, Heidelberg: Springer, pp. 305–316, doi:10.1007/978-3-642-18469-7_28, hdl:10281/217381, MR 2781275.
• Mukkamala, Padmini; Szegedy, Mario (2009), "Geometric representation of cubic graphs with four directions", Computational Geometry: Theory and Applications, 42 (9): 842–851, doi:10.1016/j.comgeo.2009.01.005, MR 2543806.
• Mukkamala, Padmini; Pálvölgyi, Dömötör (2012), "Drawing cubic graphs with the four basic slopes", in van Kreveld, Marc; Speckmann, Bettina (eds.), Graph Drawing: 19th International Symposium, GD 2011, Eindhoven, The Netherlands, September 21-23, 2011, Revised Selected Papers, Lecture Notes in Computer Science, vol. 7034, Springer, pp. 254–265, arXiv:1106.1973, doi:10.1007/978-3-642-25878-7_25.
• Pach, János; Pálvölgyi, Dömötör (2006), "Bounded-degree graphs can have arbitrarily large slope numbers", Electronic Journal of Combinatorics, 13 (1): N1, MR 2200545.
• Pach, János; Sharir, Micha (2009), "5.5 Angular resolution and slopes", Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures, Mathematical Surveys and Monographs, vol. 152, American Mathematical Society, pp. 126–127.
• Scott, P. R. (1970), "On the sets of directions determined by n points", American Mathematical Monthly, 77: 502–505, doi:10.2307/2317384, MR 0262933.
• Wade, G. A.; Chu, J.-H. (1994), "Drawability of complete graphs using a minimal slope set", The Computer Journal, 37 (2): 139–142, doi:10.1093/comjnl/37.2.139.