Title:	Computing Measures of Non-Planarity
Authors:	Wiedera, Tilo
ORCID of the author:	https://orcid.org/0000-0002-5923-4114
Thesis advisor:	Prof. Dr. Markus Chimani
Thesis referee:	Prof. Dr. Ignaz Rutter
Abstract:	Planar graphs have a rich history that dates back to the 18th Century. They form one of the core concepts of graph theory. In computational graph theory, they offer broad advantages to algorithm design and many groundbreaking results are based on them. Formally, a given graph is either planar or non-planar. However, there exists a diverse set of established measures to estimate how far away from being planar any given graph is. In this thesis, we aim at evaluating and improving algorithms to compute these measures of non-planarity. Particularly, we study (1) the problem of finding a maximum planar subgraph, i.e., a planar subgraph with the least number of edges removed; (2) the problem of embedding a graph on a lowest possible genus surface; and finally (3) the problem of drawing a graph such that there are as few edge crossings as possible. These problems constitute classical questions studied in graph drawing and each of them is NP-hard. Still, exact (exponential time) algorithms for them are of high interest and have been subject to study for decades. We propose novel mathematical programming models, based on different planarity criteria, to compute maximum planar subgraphs and low-genus embeddings. The key aspect of our most successful new models is that they carefully describe also the relation between embedded (sub-)graphs and their duals. Based on these models, we design algorithms that beat the respective state-of-the-art by orders of magnitude. We back these claims by extensive computational studies and rigorously show the theoretical advantages of our new models. Besides exact algorithms, we consider heuristic and approximate approaches to the maximum planar subgraph problem. Furthermore, in the realm of crossing numbers, we present an automated proof extraction to easily verify the crossing number of any given graph; a new hardness result for a subproblem that arises, e.g., when enumerating simple drawings; and resolve a conjecture regarding high node degree in minimal obstructions for low crossing number.
URL:	http://dx.doi.org/10.48693/9 https://osnadocs.ub.uni-osnabrueck.de/handle/ds-202112225739
Subject Keywords:	planarity; graph algorithms; algorithm engineering; maximum planar subgraph; crossing number; genus
Issue Date:	22-Dec-2021
Type of publication:	Dissertation oder Habilitation [doctoralThesis]
Appears in Collections:	FB06 - E-Dissertationen

Items in osnaDocs repository are protected by copyright, with all rights reserved, unless otherwise indicated. rightsstatements.org