این مقاله نیازمند تمیزکاری است. لطفاً تا جای امکان آنرا از نظر املا، انشا، چیدمان و درستی بهتر کنید، سپس این برچسب را بردارید. محتویات این مقاله ممکن است غیر قابل اعتماد و نادرست یا جانبدارانه باشد یا قوانین حقوق پدیدآورندگان را نقض کرده باشد.
ترسیم گراف یا گراف شبکه نمایش تصویری رئوس و لبههای یک گراف است. این طراحی نباید با خود گراف اشتباه گرفته شود: طرحبندیهای بسیار متفاوت میتوانند با یک گراف مطابقت داشته باشند.[۲] بهطور انتزاعی، تنها چیزی که اهمیت دارد این است که کدام جفت رئوس توسط یالها به هم متصل شدهاند. با این حال، در بتن، چیدمان این رئوس و لبهها در یک نقشه بر درک، قابلیت استفاده، هزینه ساخت و زیباییشناسی آن تأثیر میگذارد.[۳] اگر گراف در طول زمان با افزودن و حذف یالها تغییر کند (طراحی گراف پویا) مشکل بدتر میشود و هدف حفظ نقشه ذهنی کاربر است.[۴]
گرافها اغلب به عنوان گرافهای پیوند گره ترسیم میشوند که در آن رئوس به صورت دیسک، جعبه یا برچسبهای متنی و یالها به صورت پاره خط، چند خط یا منحنی در صفحه اقلیدسی نمایش داده میشوند.[۵] گرافهای پیوند گره را میتوان به آثار شبه یوی قرن ۱۴ تا ۱۶ که با نام رامون یوی منتشر شده بود، بازمیگردد. شبه یوی نمودارهایی از این نوع را برای نمودارهای کامل به منظور تجزیه و تحلیل تمام ترکیبات زوجی در میان مجموعهای از مفاهیم متافیزیکی ترسیم کرد.[۶]
در مورد نمودارهای جهت دار، نوک پیکانها یک قرارداد گرافیکی رایج را تشکیل میدهند تا جهت خود را نشان دهند؛[۷] با این حال، مطالعات کاربر نشان دادهاست که قراردادهای دیگر مانند مخروطی کردن این اطلاعات را بهطور مؤثرتری ارائه میدهند.[۸]ترسیم مسطح رو به بالا از این قرارداد استفاده میکند که هر یال از یک راس پایینتر به یک راس بالاتر جهتگیری میشود و نوک پیکان را غیرضروری میکند.[۹]
قراردادهای جایگزین برای نمودارهای پیوند-گره شامل نمایش مجاورتی مانند بستهبندی دایره ای است که در آن رئوس با نواحی مجزا در صفحه و یالها با مجاورتهای بین نواحی نشان داده میشوند. نمایشهای تقاطع که در آن رئوس با اجسام هندسی غیر متمایز و یالها با تقاطع آنها نشان داده میشوند. نمایشهای دید که در آن رئوس با نواحی در صفحه و لبهها با مناطقی نشان داده میشوند که یک خط دید بدون مانع نسبت به یکدیگر دارند. نقشههای همرو، که در آن لبهها به صورت منحنیهای صاف در ریلهای قطار ریاضی نمایش داده میشوند.[۱۰] پارچههایی که در آن گرهها به صورت خطوط افقی و لبهها بهعنوان خطوط عمودی نشان داده میشوند؛ و تجسمهایی از ماتریس مجاورت گراف.
در تلاش برای یافتن ابزارهای عینی برای ارزیابی زیباییشناسی و قابلیت استفاده، معیارهای کیفی مختلفی برای طراحیهای گراف تعریف شدهاند.[۱۱] علاوه بر هدایت انتخاب بین روشهای طرحبندی مختلف برای یک نمودار، برخی از روشهای طرحبندی سعی میکنند مستقیماً این معیارها را بهینه کنند.
عدد متقاطع یک رسم تعداد جفت لبههایی است که از یکدیگر عبور میکنند. اگر نمودار مسطح است، معمولاً ترسیم آن بدون هیچ گونه تقاطع لبهها راحت است؛ یعنی در این مورد، ترسیم گراف نشان دهنده تعبیه گراف است. با این حال، نمودارهای غیرمسطح اغلب در برنامههای کاربردی به وجود میآیند، بنابراین الگوریتمهای ترسیم گراف باید بهطور کلی اجازه عبور از لبه را بدهند.[۱۲]
مساحت یک نقشه به اندازه کوچکترین جعبه مرزی آن است، نسبت به نزدیکترین فاصله بین هر دو راس. طرحهایی که مساحت کمتری دارند، عموماً بر آنهایی که مساحت بزرگتری دارند ترجیح داده میشوند، زیرا به آنها اجازه میدهند ویژگیهای نقاشی در اندازه بزرگتر و بنابراین خواناتر نشان داده شوند. نسبت ابعاد جعبه مرزی نیز ممکن است مهم باشد.
نمایش تقارن مشکل یافتن گروههای تقارن در یک نمودار معین و یافتن نقاشی است که تا حد امکان تقارن را نمایش دهد. برخی از روشهای چیدمان بهطور خودکار منجر به نقشههای متقارن میشوند. بهطور متناوب، برخی از روشهای ترسیم با یافتن تقارنها در نمودار ورودی و استفاده از آنها برای ساختن یک نقشه شروع میشوند.[۱۳]
مهم است که لبهها تا حد امکان ساده باشند تا چشم راحت تر آنها را دنبال کند. در نقشههای چند خطی، پیچیدگی یک یال را میتوان با تعداد خمهای آن اندازهگیری کرد، و هدف بسیاری از روشها ارائه نقشههایی با تعداد کمی خمش یا خمهای کمی در هر لبه است. بهطور مشابه برای منحنیهای اسپلاین، پیچیدگی یک یال ممکن است با تعداد نقاط کنترل روی لبه اندازهگیری شود.
چندین معیار کیفیت که معمولاً مورد استفاده قرار میگیرند، به طول لبهها مربوط میشوند: بهطور کلی مطلوب است که طول کل لبهها و همچنین حداکثر طول هر لبه به حداقل برسد. علاوه بر این، ممکن است ترجیح داده شود که طول لبهها یکنواخت باشد تا اینکه بسیار متنوع باشد.
وضوح زاویه ای معیاری از واضحترین زوایای یک نمودار است. اگر یک نمودار دارای رئوس با درجه بالایی باشد، لزوماً وضوح زاویهای کوچکی خواهد داشت، اما وضوح زاویهای را میتوان با تابعی از درجه محدود کرد.[۱۴]
تعداد شیب یک نمودار حداقل تعداد شیب لبههای متمایز مورد نیاز در نقاشی با لبههای پاره خط مستقیم است (اجازه دادن به عبور). نمودارهای مکعبی حداکثر دارای عدد شیب چهار هستند، اما نمودارهای درجه پنج ممکن است دارای عدد شیب نامحدود باشند. اگر تعداد شیب نمودارهای درجه ۴ محدود باشد، بازمیماند.[۱۵]
↑Knuth, Donald E. (2013), "Two thousand years of combinatorics", in Wilson, Robin; Watkins, John J. (eds.), Combinatorics: Ancient and Modern, Oxford University Press, pp. 7–37.
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.
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, ISBN978-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.
Di Battista, Giuseppe; Rimondini, Massimo (2014), "Computer Networks", in Tamassia, Roberto (ed.), Handbook of Graph Drawing and Visualization, CRC Press, pp. 763–803.
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, MR2154691.
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, PMC3574047, PMID23102059.
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.
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.