Аналіз алгоритмів автоматичного укладання графів на площині в рамках задачі модифікації гамма-алгоритму

Abstract

Планарність графів – це один з ключових розділів теорії графів. Хоча граф є абстрактним математичним об'єктом, найчастіше саме візуалізація графа спрощує вивчення або розробку у певній сфері, наприклад, інфраструктури міста, менеджменту компанії або веб-сторінки сайту. Взагалі у вигляді графа можна зобразити будь-які структури, що мають зв'язки між елементами. Подібні структури через складність часто збільшуються до таких розмірів, що представлення їх на площині без перетину зв'язків стає непростим завданням. Задача укладання графа на площині не має і не може мати універсального рішення через те, що набір критеріїв, які застосовуються для оцінки якості укладання, залежить від конкретної сфери застосування. Такими критеріями, наприклад, можуть бути мінімізація площини, що за- ймає укладений граф, мінімізація кількості зламів, мінімізація загальної довжини ребер тощо. Розглянемо дві групи алгоритмів укладання графів, що принципово відрізняються підходом до рішення задачі: алгоритми з фізичним аналогом та аналітичні алгоритми.