Modification of the analytical gamma-algorithm for the flat layout of the graph

Abstract

The planarity of graphs is one of the key sections of graph theory. Although a graph is an abstract mathematical object, most often it is graph visualization that makes it easier to study or develop in a particular area, for example, the infrastructure of a city, a company’s management or a website’s web page. In general, in the form of a graph, it is possible to depict any structures that have connections between the elements. But often such structures grow to such dimensions that it is difficult to determine whether it is possible to represent them on a plane without intersecting the bonds. There are many algorithms that solve this issue. One of these is the gamma method. The article identifies its problems and suggests methods for solving them, and also examines ways to achieve them. Планарність графів – це один із ключових розділів теорії графів. Хоча граф є абстрактним математичним об’єктом, найчастіше саме візуалізація графа спрощує вивчення або розробку у певній сфері, наприклад, інфраструктури міста, менеджменту компанії або веб-сторінки сайту. Взагалі у вигляді графа можна зобразити будь-які структури, що мають зв’язки між елементами. Але часто подібні структури збільшуються до таких розмірів, що важко визначити, чи можливо представити їх на площині без перетину зв’язків. Існує багато алгоритмів, що вирішують це питання. Одним із таких є гамма-алгоритм. У статті визначені його проблеми та запропоновані методи їх вирішення, а також досліджені шляхи їх досягнення.