Heuristic optimization of graph embedding problems in circular layouts

Abstract

Optimization is a discipline that addresses the search for the best possible solution, called the optimal solution, to a problem mathematically modeled. These problems can be classified according to its computational complexity. Problems belonging to the NP-hard class are too complex to be solved with an exact algorithm in a reasonable amount of time. Alternatively, these problems can be approached through approximate techniques that allow finding good quality solutions, although not necessarily optimal, in a reasonable amount of computing time. Among these techniques, heuristic and metaheuristic algorithms stand out, since they have been proven as useful tools in solving high-complexity real problems. In this Doctoral Thesis, heuristic and metaheuristic algorithms are proposed for the resolution of four Graph Layout Problems (GLP). Specifically, the problems studied belong to the NP-hard class and can be framed as combinatorial optimization problems. GLPs aim to find the best possible assignment of the vertices of an input graph to the vertices of a host graph, optimizing a certain objective function. More specifically, this Doctoral Thesis focuses on the study of GLPs in which the embedding is done in circular layouts. This family of problems is of great interest due to the variety of practical applications they have. In this research, a methodology for addressing GLPs is proposed. Specifically, it starts from the study of each problem, and then proposes heuristic and metaheuristic algorithms for tackling the problem. After a preliminary experimentation, the algorithmic proposal is compared to the existing methods in the state of the art. This methodology has been successfully applied to the studied problems, resulting in various scientific publications that compile the main findings of the research carried out.