वृत्ताकार विन्यास
ग्राफ रेखाचित्र में, वृत्ताकार विन्यास(लेआउट) रेखाचित्र की एक शैली है जो ग्राफ सिद्धांत के शीर्ष (ग्राफ सिद्धांत) को वृत्त पर रखती है, वे एक नियमित बहुभुज के शीर्षों का निर्माण कर सकें इसलिए यह प्रायः समान दूरी पर होती है।
अनुप्रयोग
वृत्ताकार विन्यास संचार संजाल सांस्थिति जैसे तारक संजाल या चक्राकार संजाल[1] और उपापचयी संजाल के चक्रीय भागों के लिए उपयुक्त हैं।[2] ज्ञात हैमिल्टनियन चक्र वाले ग्राफ़ के लिए, वृत्ताकार विन्यास चक्र को वृत्त के रूप में चित्रित करने की अनुमति देता है, और इस तरह परिपत्र विन्यास हैमिल्टनियन घन ग्राफ के लिए एलसीएफ(LCF) संकेतन का आधार बनाते हैं।[3]
वृत्ताकार विन्यास का उपयोग संपूर्ण ग्राफ़ रेखाचित्र के लिए किया जा सकता है, लेकिन इसका उपयोग बड़े ग्राफ़ रेखाचित्र के भीतर शीर्षों के छोटे समूहों के लिए विन्यास के रूप में भी किया जा सकता है, जैसे कि इसके द्विसंबद्ध घटक,[4] जीन में जीन के समूह परस्पर क्रिया ग्राफ़,[5] या किसी सामाजिक संजाल के भीतर प्राकृतिक उपसमूह के रूप में भी किया जा सकता है।[6] यदि इस तरह से एकाधिक शीर्ष वृत्तों का उपयोग किया जाता है, तो समूहों को व्यवस्थित करने के लिए बल-निर्देशित ग्राफ़ रेखाचित्र जैसी अन्य विधियों का उपयोग किया जा सकता है।[7]
इनमें से कुछ अनुप्रयोगों, जैसे जैव सूचना विज्ञान या सामाजिक प्रत्योक्षकरण संजाल में वृत्ताकार विन्यास का लाभ इसकी तटस्थता है:[8] सभी शीर्षों को एक-दूसरे से और रेखाचित्र के केंद्र से समान दूरी पर रखकर, किसी को भी विशेषाधिकार प्राप्त स्थान नहीं दिया जाता है, जिससे दर्शकों की केंद्रीय रूप से स्थित ग्रंथि को अधिक महत्वपूर्ण मानने की प्रवृत्ति का प्रतिद्विंद्विता होता है।[9]
किनारे शैली
रेखा-चित्र के किनारों को वृत्त की जीवा ,[10]वृत्ताकार चाप [11](संभवतः शीर्ष वृत्त के लंबवत, ताकि किनारे अतिशयोक्तिपूर्ण ज्यामिति के पोइंकारे डिस्क प्रतिरूप की प्रतिरूप रेखाएं हों), या अन्य प्रकार के वक्र के रूप में दर्शाया जा सकता है।[12]
एक वृत्ताकार विन्यास में शीर्ष वृत्त के अंदर और बाहर के बीच दृश्य अंतर का उपयोग किनारे की रेखाचित्र की दो अलग-अलग शैलियों को अलग करने के लिए किया जा सकता है। उदाहरण के लिए, गैन्सनर और कोरेन का एक वृत्ताकार रेखाचित्र कलनविधि वृत्त के भीतर किनारे पुलिंदा का उपयोग करता है, साथ में कुछ किनारों को जो पुलिंदा नहीं किया गया है, उन्हें वृत्त के बाहर खींचा जाता है।[12]
नियमित ग्राफ के वृत्ताकार विन्यास के लिए, जिसके किनारों को अंदर और बाहर दोनों ओर वृत्ताकार चाप के रूप में खींचा गया है, शीर्ष वृत्त के साथ इन चापों में से एक का आपतन कोण चाप के दोनों सिरों पर समान होता है, ऐसे गुणधर्म जो रेखा-चित्र के कोणीय प्रस्ताव के अनुकूलन को सरल बनाती है।
रेखण की संख्या
अनेक लेखकों ने एक वृत्ताकार विन्यास के शीर्षों के क्रमपरिवर्तन के अन्वेषण की समस्या का अध्ययन किया है जो कि शीर्ष वृत्त के अंदर सभी किनारों को खींचे जाने पर किनारे रेखण की संख्या को कम करता है। रेखण की यह संख्या केवल बाहरी तलीय ग्राफ़ के लिए शून्य है।[13] अन्य ग्राफ़ के लिए, समाधानों को संयोजित करने से पहले ग्राफ़ के प्रत्येक द्वि-जुड़े घटक के लिए इसे अलग से अनुकूलित या कम किया जा सकता है,जिससे वे परस्पर क्रिया न करें क्योंकि इन घटकों को खींचा जा सकता है ।[14]
सामान्यतः, रेखण की संख्या को न्यूनतम करना NP-पूर्ण है,[15] लेकिन इसे O(log2 n) के अनुमानित अनुपात के साथ अनुमानित किया जा सकता है जहां n शीर्षों की संख्या है।[16] रेखण जटिलता को कम करने के लिए अनुमानी विधि भी उद्यत किए गए हैं, उदाहरण के लिए,सावधानीपूर्वक शीर्ष सम्मिलन क्रम पर और स्थानीय अनुकूलन पर उद्यत किया गया हैं।[17]
रेखण की संख्या को अधिकतम करने के लिए एक वृत्ताकार विन्यास का भी उपयोग किया जा सकता है। विशेष रूप से, शीर्षों के लिए एक यादृच्छिक क्रमपरिवर्तन चुनने से प्रत्येक संभावित रेखण संभावना 1/3 के साथ होती है, इसलिए रेखण का अपेक्षित मूल्य सभी संभावित विन्यास के बीच रेखण की अधिकतम संख्या के तीन के एक कारक के भीतर होता है। इस पद्धति को व्युत्पन्न करने से सन्निकटन अनुपात तीन के साथ एक नियतात्मक सन्निकटन कलनविधि मिलता है।[18]
अन्य अनुकूलन मानदंड
रेखण के साथ-साथ, एक वृत्ताकार विन्यास में किनारों की लंबाई को अनुकूलित करने की समस्याओं के वृत्ताकार संस्करण, रेखण के कोणीय प्रस्ताव, या कटविड्थ (किनारों की अधिकतम संख्या जो वृत्त के एक चाप को विपरीत चाप से जोड़ती है) पर भी विचार किया गया है,[19] लेकिन इनमें से अनेक समस्याएं NP-पूर्ण हैं।[20]
यह भी देखें
- कॉर्ड आरेख (सूचना प्रत्योक्षकरण), सूचना प्रत्योक्षकरण में एक निकट से संबंधित अवधारणा
- समतलता, एक पहेली जिसमें एक खिलाड़ी को एक यादृच्छिक वृत्ताकार विन्यास से शुरू करते हुए, एक समतलीय ग्राफ के चित्र को सुलझाने के लिए शीर्षों को घुमाना होता है
बाहरी संबंध
टिप्पणियाँ
- ↑ Doğrusöz, Madden & Madden (1997).
- ↑ Becker & Rojas (2001).
- ↑ Pisanski & Servatius (2013).
- ↑ Doğrusöz, Madden & Madden (1997); Six & Tollis (1999b).
- ↑ Symeonidis & Tollis (2004).
- ↑ Krebs (1996).
- ↑ Doğrusöz, Belviranli & Dilek (2012).
- ↑ Iragne et al. (2005).
- ↑ Huang, Hong & Eades (2007).
- ↑ Six & Tollis (1999a).
- ↑ Duncan et al. (2012).
- ↑ 12.0 12.1 Gansner & Koren (2007).
- ↑ Six & Tollis (1999a); Baur & Brandes (2005).
- ↑ Baur & Brandes (2005).
- ↑ Masuda et al. (1987).
- ↑ Shahrokhi et al. (1995).
- ↑ Mäkinen (1988); Doğrusöz, Madden & Madden (1997); Six & Tollis (1999a); He & Sýkora (2004); Baur & Brandes (2005).
- ↑ Verbitsky (2008).
- ↑ Mäkinen (1988); Gansner & Koren (2007); Nguyen et al. (2011); Dehkordi et al. (2013).
- ↑ Mäkinen (1988).
संदर्भ
- Baur, Michael; Brandes, Ulrik (2005), "Crossing reduction in circular layouts", in van Leeuwen, Jan (ed.), Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers, Lecture Notes in Computer Science, vol. 3353, Springer, pp. 332–343, doi:10.1007/978-3-540-30559-0_28.
- Becker, Moritz Y.; Rojas, Isabel (2001), "A graph layout algorithm for drawing metabolic pathways", Bioinformatics, 17 (5): 461–467, doi:10.1093/bioinformatics/17.5.461, PMID 11331241.
- Dehkordi, Hooman Reisi; Nguyen, Quan; Eades, Peter; Hong, Seok-Hee (2013), "Circular graph drawings with large crossing angles", Algorithms and Computation: 7th International Workshop, WALCOM 2013, Kharagpur, India, February 14-16, 2013, Proceedings, Lecture Notes in Computer Science, vol. 7748, Springer, pp. 298–309, doi:10.1007/978-3-642-36065-7_28.
- Doğrusöz, Uğur; Belviranli, M.; Dilek, A. (2012), "CiSE: A circular spring embedder layout algorithm", IEEE Transactions on Visualization and Computer Graphics, 19 (6): 953–966, doi:10.1109/TVCG.2012.178, hdl:11693/21006, PMID 23559509, S2CID 14365664.
- Doğrusöz, Uğur; Madden, Brendan; Madden, Patrick (1997), "Circular layout in the Graph Layout toolkit", Graph Drawing: Symposium on Graph Drawing, GD '96, Berkeley, California, USA, September 18–20, 1996, Proceedings, Lecture Notes in Computer Science, vol. 1190, Springer, pp. 92–100, doi:10.1007/3-540-62495-3_40.
- Duncan, Christian A.; Eppstein, David; Goodrich, Michael T.; Kobourov, Stephen G.; Nöllenburg, Martin (2012), "Lombardi drawings of graphs", Journal of Graph Algorithms and Applications, 16 (1): 85–108, arXiv:1009.0579, doi:10.7155/jgaa.00251, S2CID 5000926.
- Gansner, Emden R.; Koren, Yehuda (2007), Graph Drawing: 14th International Symposium, GD 2006, Karlsruhe, Germany, September 18-20, 2006, Revised Papers, Lecture Notes in Computer Science, vol. 4372, Springer, pp. 386–398, doi:10.1007/978-3-540-70904-6_37.
- He, H.; Sýkora, Ondrej (2004), "New circular drawing algorithms", Proceedings of the Workshop on Information Technologies – Applications and Theory (ITAT), Slovakia, September 15-19.
- Huang, Weidong; Hong, Seok-Hee; Eades, Peter (2007), "Effects of sociogram drawing conventions and edge crossings in social network visualization", Journal of Graph Algorithms and Applications, 11 (2): 397–429, doi:10.7155/jgaa.00152.
- Iragne, Florian; Nikolski, Macha; Mathieu, Bertrand; Auber, David; Sherman, David (2005), "ProViz: protein interaction visualization and exploration", Bioinformatics, 21 (2): 272–274, doi:10.1093/bioinformatics/bth494, PMID 15347570.
- Krebs, Valdis (1996), "Visualizing human networks" (PDF), Release 1.0: Esther Dyson's Monthly Report, 2–96.
- Mäkinen, Erkki (1988), "On circular layouts", International Journal of Computer Mathematics, 24 (1): 29–37, doi:10.1080/00207168808803629.
- Masuda, S.; Kashiwabara, T.; Nakajima, K.; Fujisawa, T. (1987), "On the NP-completeness of a computer network layout problem", Proceedings of the IEEE International Symposium on Circuits and Systems, pp. 292–295. As cited by Baur & Brandes (2005).
- Nguyen, Quan; Eades, Peter; Hong, Seok-Hee; Huang, Weidong (2011), "Large crossing angles in circular layouts", Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010, Revised Selected Papers, Lecture Notes in Computer Science, vol. 6502, Springer, pp. 397–399, doi:10.1007/978-3-642-18469-7_40.
- Pisanski, Tomaž; Servatius, Brigitte (2013), "2.3.2 Cubic graphs and LCF notation", Configurations from a Graphical Viewpoint, Springer, p. 32, ISBN 9780817683641.
- Shahrokhi, Farhad; Sýkora, Ondrej; Székely, László A.; Vrt'o, Imrich (1995), "Book embeddings and crossing numbers", Graph-Theoretic Concepts in Computer Science: 20th International Workshop, WG '94, Herrsching, Germany, June 16–18, 1994, Proceedings, Lecture Notes in Computer Science, vol. 903, Springer, pp. 256–268, doi:10.1007/3-540-59071-4_53.
- Six, Janet M.; Tollis, Ioannis G. (1999a), "Circular drawings of biconnected graphs", Algorithm Engineering and Experimentation: International Workshop ALENEX'99, Baltimore, MD, USA, January 15–16, 1999, Selected Papers, Lecture Notes in Computer Science, vol. 1619, Springer, pp. 57–73, doi:10.1007/3-540-48518-X_4.
- Six, Janet M.; Tollis, Ioannis G. (1999b), "A framework for circular drawings of networks", Graph Drawing: 7th International Symposium, GD'99, Štiřín Castle, Czech Republic, September 15–19, 1999, Proceedings, Lecture Notes in Computer Science, vol. 1731, Springer, pp. 107–116, doi:10.1007/3-540-46648-7_11.
- Symeonidis, Alkiviadis; Tollis, Ioannis G. (2004), "Visualization of biological information with circular drawings", Biological and Medical Data Analysis: 5th International Symposium, ISBMDA 2004, Barcelona, Spain, November 18-19, 2004, Proceedings, Lecture Notes in Computer Science, vol. 3337, Springer, pp. 468–478, doi:10.1007/978-3-540-30547-7_47.
- Verbitsky, Oleg (2008), "On the obfuscation complexity of planar graphs", Theoretical Computer Science, 396 (1–3): 294–300, arXiv:0705.3748, doi:10.1016/j.tcs.2008.02.032, MR 2412266, S2CID 5948167.
