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

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

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

पूर्ण ग्राफ़

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

इस प्रकार से ग्राफ़ की ढलान संख्या निर्धारित करने की समस्या किसके द्वारा प्रस्तुत की गई थी? वेड & चू (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)

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

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

समतलीय रेखांकन

जैसा केसज़ेग, पच & पाल्वोल्ग्यी (2011) दिखाया गया है, प्रत्येक समतलीय ग्राफ में फ़ेरी का प्रमेय होता है और तलीय सीधी-रेखा रेखाचित्र जिसमें अलग-अलग ढलानों की संख्या ग्राफ़ की डिग्री का कार्य है। इस तरह से प्रमाण निर्माण का अनुसरण करता है मालित्ज़ & पापाकोस्टास (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.