Approximation Algorithms for Some Topological Invariants of Graphs

Abstract

Topologinen graafiteoria tutkii graafien kuvauksia erilaisille pinnoille sekä näiden kuvausten ominaisuuksia. Porasen tietojenkäsittelytieteellisessä työssä on tarkasteltu isomorfisissa graafeissa muuttumattomina pysyvien topologisten ominaisuuksien tunnistamista. Tutkituilla algoritmeilla on sovelluksia graafien visualisoinnissa, piirilevyjen suunnittelussa sekä erilaisissa sijoitteluongelmissa.

Työssä esitetään useita uusia likimääräismenetelmiä seuraavien graafien topologisten ominaisuuksien laskemiseksi: suurimman tasoaligraafin koko, suurimman ulkotasoaligraafin koko, graafin paksuus ja ulkopaksuus. Näistä ongelmista kolme ensimmäistä kuuluu laskennallisesti vaikeiden eli NP-täydellisten ongelmien luokkaan. Ulkopaksuuden määräämisen laskennallista vaativuutta ei tunneta.

Uusia menetelmiä verrataan kirjallisuudessa aiemmin esitettyihin menetelmiin ja osoitetaan että kehitetyt algoritmit toimivat aiempia menetelmiä tehokkaammin sekä suoritusajan että ratkaisujen hyvyyden suhteen.

Lisäksi työssä esitetään myös uusia teoreettisia tuloksia graafin ulkopaksuden ylä- ja alarajan sekä kolmijakoisten graafien paksuuden ylärajan arviointiin. Työssä ratkaistaan osittain myös yli kolmekymmentä vuotta avoimena ollut kaksijakoisten graafien paksuuteen liittyvä ongelma.

Topological graph theory studies the embeddings of graphs on various surfaces and the properties of these embeddings. Topological properties of graphs have many applications in the fields of graph drawing, user interface design, circuit design, and resource location optimization.

This thesis studies approximation methods for the following \NP-complete optimization problems: maximum planar subgraph, maximum outerplanar subgraph, and thickness of a graph. We also study the outerthickness problem which complexity status is not known. We compare the solution quality and computation times of a simulated annealing algorithm and several algorithms based on triangular cactus heuristic, including other heuristics taken from the literature, to approximately solve these problems.

Triangular cactus heuristic was the first non-trivial approximation algorithm for the maximum planar and outerplanar subgraph problems. We give a modified version of the triangular cactus heuristic that has at least equal performance ratio and asymptotic running time as the linear time version of the original algorithm. A large number of experiments show that the new algorithm achieves better approximations than the earlier methods.

We give two new theoretical results for the thickness and outerthickness of a graph. We prove a new upper bound for the thickness of complete tripartite graphs, and lower and upper bounds in the terms of the minimum and maximum degree of a graph for outerthickness. Also, the simulated annealing algorithm given in this work solves partially an open problem related to the thickness of the complete bipartite graphs. Our experiments show that the general formula also holds for some previously unknown cases.