ترسیم گراف در چند ضلعی حفره دار توسط الگوریتم ژنتیکی

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

کلیدواژه ها:

کمیته ژنتیک ، ترسیم گراف ، چند ضلعی حفره دار