رسم گراف

ترسیم گراف حوزه ای از ریاضیات و علوم کامپیوتر است که روش‌های تئوری نمودار هندسی و تجسم اطلاعات را برای به دست آوردن تصاویر دو بعدی از گراف‌ها که از کاربردهایی مانند تجزیه و تحلیل شبکه‌های اجتماعی، کارتوگرافی، زبان‌شناسی و بیوانفورماتیک ناشی می‌شود، ترکیب می‌کند.

ترسیم گراف یا گراف شبکه نمایش تصویری رئوس و لبه‌های یک گراف است. این طراحی نباید با خود گراف اشتباه گرفته شود: طرح‌بندی‌های بسیار متفاوت می‌توانند با یک گراف مطابقت داشته باشند. به‌طور انتزاعی، تنها چیزی که اهمیت دارد این است که کدام جفت رئوس توسط یال‌ها به هم متصل شده‌اند. با این حال، در بتن، چیدمان این رئوس و لبه‌ها در یک نقشه بر درک، قابلیت استفاده، هزینه ساخت و زیبایی‌شناسی آن تأثیر می‌گذارد. اگر گراف در طول زمان با افزودن و حذف یال‌ها تغییر کند (طراحی گراف پویا) مشکل بدتر می‌شود و هدف حفظ نقشه ذهنی کاربر است.

قراردادهای گرافیکی

گراف‌ها اغلب به عنوان گراف‌های پیوند گره ترسیم می‌شوند که در آن رئوس به صورت دیسک، جعبه یا برچسب‌های متنی و یال‌ها به صورت پاره خط، چند خط یا منحنی در صفحه اقلیدسی نمایش داده می‌شوند. گراف‌های پیوند گره را می‌توان به آثار شبه یوی قرن ۱۴ تا ۱۶ که با نام رامون یوی منتشر شده بود، بازمی‌گردد. شبه یوی نمودارهایی از این نوع را برای نمودارهای کامل به منظور تجزیه و تحلیل تمام ترکیبات زوجی در میان مجموعه‌ای از مفاهیم متافیزیکی ترسیم کرد.

در مورد نمودارهای جهت دار، نوک پیکان‌ها یک قرارداد گرافیکی رایج را تشکیل می‌دهند تا جهت خود را نشان دهند؛ با این حال، مطالعات کاربر نشان داده‌است که قراردادهای دیگر مانند مخروطی کردن این اطلاعات را به‌طور مؤثرتری ارائه می‌دهند. ترسیم مسطح رو به بالا از این قرارداد استفاده می‌کند که هر یال از یک راس پایین‌تر به یک راس بالاتر جهت‌گیری می‌شود و نوک پیکان را غیرضروری می‌کند.

قراردادهای جایگزین برای نمودارهای پیوند-گره شامل نمایش مجاورتی مانند بسته‌بندی دایره ای است که در آن رئوس با نواحی مجزا در صفحه و یال‌ها با مجاورت‌های بین نواحی نشان داده می‌شوند. نمایش‌های تقاطع که در آن رئوس با اجسام هندسی غیر متمایز و یال‌ها با تقاطع آنها نشان داده می‌شوند. نمایش‌های دید که در آن رئوس با نواحی در صفحه و لبه‌ها با مناطقی نشان داده می‌شوند که یک خط دید بدون مانع نسبت به یکدیگر دارند. نقشه‌های همرو، که در آن لبه‌ها به صورت منحنی‌های صاف در ریل‌های قطار ریاضی نمایش داده می‌شوند. پارچه‌هایی که در آن گره‌ها به صورت خطوط افقی و لبه‌ها به‌عنوان خطوط عمودی نشان داده می‌شوند؛ و تجسم‌هایی از ماتریس مجاورت گراف.

معیارهای کیفیت

در تلاش برای یافتن ابزارهای عینی برای ارزیابی زیبایی‌شناسی و قابلیت استفاده، معیارهای کیفی مختلفی برای طراحی‌های گراف تعریف شده‌اند. علاوه بر هدایت انتخاب بین روش‌های طرح‌بندی مختلف برای یک نمودار، برخی از روش‌های طرح‌بندی سعی می‌کنند مستقیماً این معیارها را بهینه کنند.

• عدد متقاطع یک رسم تعداد جفت لبه‌هایی است که از یکدیگر عبور می‌کنند. اگر نمودار مسطح است، معمولاً ترسیم آن بدون هیچ گونه تقاطع لبه‌ها راحت است؛ یعنی در این مورد، ترسیم گراف نشان دهنده تعبیه گراف است. با این حال، نمودارهای غیرمسطح اغلب در برنامه‌های کاربردی به وجود می‌آیند، بنابراین الگوریتم‌های ترسیم گراف باید به‌طور کلی اجازه عبور از لبه را بدهند.
• مساحت یک نقشه به اندازه کوچک‌ترین جعبه مرزی آن است، نسبت به نزدیکترین فاصله بین هر دو راس. طرح‌هایی که مساحت کمتری دارند، عموماً بر آن‌هایی که مساحت بزرگ‌تری دارند ترجیح داده می‌شوند، زیرا به آنها اجازه می‌دهند ویژگی‌های نقاشی در اندازه بزرگ‌تر و بنابراین خواناتر نشان داده شوند. نسبت ابعاد جعبه مرزی نیز ممکن است مهم باشد.
• نمایش تقارن مشکل یافتن گروه‌های تقارن در یک نمودار معین و یافتن نقاشی است که تا حد امکان تقارن را نمایش دهد. برخی از روش‌های چیدمان به‌طور خودکار منجر به نقشه‌های متقارن می‌شوند. به‌طور متناوب، برخی از روش‌های ترسیم با یافتن تقارن‌ها در نمودار ورودی و استفاده از آن‌ها برای ساختن یک نقشه شروع می‌شوند.
• مهم است که لبه‌ها تا حد امکان ساده باشند تا چشم راحت تر آنها را دنبال کند. در نقشه‌های چند خطی، پیچیدگی یک یال را می‌توان با تعداد خم‌های آن اندازه‌گیری کرد، و هدف بسیاری از روش‌ها ارائه نقشه‌هایی با تعداد کمی خمش یا خم‌های کمی در هر لبه است. به‌طور مشابه برای منحنی‌های اسپلاین، پیچیدگی یک یال ممکن است با تعداد نقاط کنترل روی لبه اندازه‌گیری شود.
• چندین معیار کیفیت که معمولاً مورد استفاده قرار می‌گیرند، به طول لبه‌ها مربوط می‌شوند: به‌طور کلی مطلوب است که طول کل لبه‌ها و همچنین حداکثر طول هر لبه به حداقل برسد. علاوه بر این، ممکن است ترجیح داده شود که طول لبه‌ها یکنواخت باشد تا اینکه بسیار متنوع باشد.
• وضوح زاویه ای معیاری از واضح‌ترین زوایای یک نمودار است. اگر یک نمودار دارای رئوس با درجه بالایی باشد، لزوماً وضوح زاویه‌ای کوچکی خواهد داشت، اما وضوح زاویه‌ای را می‌توان با تابعی از درجه محدود کرد.
• تعداد شیب یک نمودار حداقل تعداد شیب لبه‌های متمایز مورد نیاز در نقاشی با لبه‌های پاره خط مستقیم است (اجازه دادن به عبور). نمودارهای مکعبی حداکثر دارای عدد شیب چهار هستند، اما نمودارهای درجه پنج ممکن است دارای عدد شیب نامحدود باشند. اگر تعداد شیب نمودارهای درجه ۴ محدود باشد، بازمی‌ماند.

منابع

• Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1994), "Algorithms for Drawing Graphs: an Annotated Bibliography", Computational Geometry: Theory and Applications, 4 (5): 235–282, doi:10.1016/0925-7721(94)00014-x, archived from the original on 2016-03-27, retrieved 2007-03-19.
• Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1998), Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, ISBN 978-0-13-301615-4.
• Herman, Ivan; Melançon, Guy; Marshall, M. Scott (2000), "Graph Visualization and Navigation in Information Visualization: A Survey", IEEE Transactions on Visualization and Computer Graphics, 6 (1): 24–43, doi:10.1109/2945.841119.
• Jünger, Michael; Mutzel, Petra (2004), Graph Drawing Software, Springer-Verlag, ISBN 978-3-540-00881-1.
• Kaufmann, Michael; Wagner, Dorothea, eds. (2001), Drawing Graphs: Methods and Models, Lecture Notes in Computer Science, vol. 2025, Springer-Verlag, doi:10.1007/3-540-44969-8, ISBN 978-3-540-42062-0, S2CID 1808286.
• Tamassia, Roberto, ed. (2014), Handbook of Graph Drawing and Visualization, CRC Press, archived from the original on 2013-08-15, retrieved 2013-08-28.

زیرجستار تخصصی

• Anderson, James Andrew; Head, Thomas J. (2006), Automata Theory with Modern Applications, Cambridge University Press, pp. 38–41, ISBN 978-0-521-84887-9.
• Bachmaier, Christian; Brandes, Ulrik; Schreiber, Falk (2014), "Biological Networks", in Tamassia, Roberto (ed.), Handbook of Graph Drawing and Visualization, CRC Press, pp. 621–651.
• Bastert, Oliver; Matuszewski, Christian (2001), "Layered drawings of digraphs", in Kaufmann, Michael; Wagner, Dorothea (eds.), Drawing Graphs: Methods and Models, Lecture Notes in Computer Science, vol. 2025, Springer-Verlag, pp. 87–120, doi:10.1007/3-540-44969-8_5, ISBN 978-3-540-42062-0.
• Beckman, Brian (1994), Theory of Spectral Graph Layout, Tech. Report MSR-TR-94-04, Microsoft Research, archived from the original on 2016-04-01, retrieved 2011-09-17.
• Brandes, Ulrik; Freeman, Linton C.; Wagner, Dorothea (2014), "Social Networks", in Tamassia, Roberto (ed.), Handbook of Graph Drawing and Visualization, CRC Press, pp. 805–839.
• Di Battista, Giuseppe; Rimondini, Massimo (2014), "Computer Networks", in Tamassia, Roberto (ed.), Handbook of Graph Drawing and Visualization, CRC Press, pp. 763–803.
• Doğrusöz, Uğur; Madden, Brendan; Madden, Patrick (1997), "Circular layout in the Graph Layout toolkit", in North, Stephen (ed.), Symposium on Graph Drawing, GD '96 Berkeley, California, USA, September 18–20, 1996, Proceedings, Lecture Notes in Computer Science, vol. 1190, Springer-Verlag, pp. 92–100, doi:10.1007/3-540-62495-3_40, ISBN 978-3-540-62495-0.
• Eiglsperger, Markus; Fekete, Sándor; Klau, Gunnar (2001), "Orthogonal graph drawing", in Kaufmann, Michael; Wagner, Dorothea (eds.), Drawing Graphs, Lecture Notes in Computer Science, vol. 2025, Springer Berlin / Heidelberg, pp. 121–171, doi:10.1007/3-540-44969-8_6, ISBN 978-3-540-42062-0.
• Freese, Ralph (2004), "Automated lattice drawing", in Eklund, Peter (ed.), Concept Lattices: Second International Conference on Formal Concept Analysis, ICFCA 2004, Sydney, Australia, February 23-26, 2004, Proceedings (PDF), Lecture Notes in Computer Science, vol. 2961, Springer-Verlag, pp. 589–590, CiteSeerX 10.1.1.69.6245, doi:10.1007/978-3-540-24651-0_12, ISBN 978-3-540-21043-6, archived (PDF) from the original on 2016-03-14, retrieved 2011-09-17.
• Garg, Ashim; Tamassia, Roberto (1995), "Upward planarity testing", Order, 12 (2): 109–133, CiteSeerX 10.1.1.10.2237, doi:10.1007/BF01108622, MR 1354797, S2CID 14183717.
• Holten, Danny; Isenberg, Petra; van Wijk, Jarke J.; Fekete, Jean-Daniel (2011), "An extended evaluation of the readability of tapered, animated, and textured directed-edge representations in node-link graphs", IEEE Pacific Visualization Symposium (PacificVis 2011) (PDF), pp. 195–202, doi:10.1109/PACIFICVIS.2011.5742390, ISBN 978-1-61284-935-5, S2CID 16526781, archived (PDF) from the original on 2016-04-11, retrieved 2011-09-29.
• Holten, Danny; van Wijk, Jarke J. (2009), "A user study on visualizing directed edges in graphs", Proceedings of the 27th International Conference on Human Factors in Computing Systems (CHI '09) (PDF), pp. 2299–2308, CiteSeerX 10.1.1.212.5461, doi:10.1145/1518701.1519054, ISBN 978-1-60558-246-7, S2CID 9725345, archived from the original (PDF) on 2011-11-06.
• Koren, Yehuda (2005), "Drawing graphs by eigenvectors: theory and practice", Computers & Mathematics with Applications, 49 (11–12): 1867–1888, doi:10.1016/j.camwa.2004.08.015, MR 2154691.
• Longabaugh, William (2012), "Combing the hairball with BioFabric: a new approach for visualization of large networks", BMC Bioinformatics, 13: 275, doi:10.1186/1471-2105-13-275, PMC 3574047, PMID 23102059.
• Madden, Brendan; Madden, Patrick; Powers, Steve; Himsolt, Michael (1996), "Portable graph layout and editing", in Brandenburg, Franz J. (ed.), Graph Drawing: Symposium on Graph Drawing, GD '95, Passau, Germany, September 20–22, 1995, Proceedings, Lecture Notes in Computer Science, vol. 1027, Springer-Verlag, pp. 385–395, doi:10.1007/BFb0021822, ISBN 978-3-540-60723-6.
• Misue, K.; Eades, P.; Lai, W.; Sugiyama, K. (1995), "Layout Adjustment and the Mental Map", Journal of Visual Languages & Computing, 6 (2): 183–210, doi:10.1006/jvlc.1995.1010.
• Nachmanson, Lev; Robertson, George; Lee, Bongshin (2008), "Drawing Graphs with GLEE" (PDF), in Hong, Seok-Hee; Nishizeki, Takao; Quan, Wu (eds.), Graph Drawing, 15th International Symposium, GD 2007, Sydney, Australia, September 24–26, 2007, Revised Papers, Lecture Notes in Computer Science, vol. 4875, Springer-Verlag, pp. 389–394, doi:10.1007/978-3-540-77537-9_38, ISBN 978-3-540-77536-2.
• 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.
• Purchase, H. C.; Cohen, R. F.; James, M. I. (1997), "An experimental study of the basis for graph drawing algorithms" (PDF), Journal of Experimental Algorithmics, 2, Article 4, doi:10.1145/264216.264222, S2CID 22076200.
• Saaty, Thomas L. (1964), "The minimum number of intersections in complete graphs", Proc. Natl. Acad. Sci. U.S.A., 52 (3): 688–690, Bibcode:1964PNAS...52..688S, doi:10.1073/pnas.52.3.688, PMC 300329, PMID 16591215.
• Scott, John (2000), "Sociograms and Graph Theory", Social network analysis: a handbook (2nd ed.), Sage, pp. 64–69, ISBN 978-0-7619-6339-4.
• Sugiyama, Kozo; Tagawa, Shôjirô; Toda, Mitsuhiko (1981), "Methods for visual understanding of hierarchical system structures", IEEE Transactions on Systems, Man, and Cybernetics, SMC-11 (2): 109–125, doi:10.1109/TSMC.1981.4308636, MR 0611436, S2CID 8367756.
• Tantau, Till (2013), "Graph Drawing in TikZ", Journal of Graph Algorithms and Applications, 17 (4): 495–513, doi:10.7155/jgaa.00301.
• Zapponi, Leonardo (August 2003), "What is a Dessin d'Enfant" (PDF), Notices of the American Mathematical Society, 50: 788–789, archived (PDF) from the original on 2021-10-03, retrieved 2021-04-28.

پیوند به بیرون

• GraphX library for .NET بایگانی‌شده در ۲۰۱۸-۰۱-۲۶ توسط Wayback Machine: کتابخانه منبع باز WPF برای محاسبه و تجسم نمودار. پشتیبانی از بسیاری از الگوریتم‌های طرح‌بندی و مسیریابی لبه.
• آرشیو چاپ الکترونیکی ترسیم نمودار: شامل اطلاعات روی مقالات از تمام سمپوزیوم‌های گراف طراحی.
• رسم گراف در کرلی برای بسیاری از پیوندهای اضافی مربوط به رسم گراف.