Plane and simple : using planar subgraphs for efficient algorithms

Abstract

In this thesis, we showcase how planar subgraphs with special structural properties can be used to fi nd efficient algorithms for two NP-hard problems in combinatorial optimization. In the fi rst part, we develop algorithms for the computation of Tutte paths and show how these special subgraphs can be used to efficiently compute long cycles and other relaxations of Hamiltonicity if we restrict the input to planar graphs. We give an O(n^2) time algorithm for the computation of Tutte paths in circuit graphs and generalize it to the computation of Tutte paths between any two given vertices and a prescribed intermediate edge in 2-connected planar graphs. In the second part, we study the Maximum Planar Subgraph Problem (MPS) and show how dense planar subgraphs can be used to develop new approximation algorithms for this problem. All new algorithms and arguments we present are based on a novel approach that focuses on maximizing the number of triangular faces in the computed subgraph. For this, we define a new optimization problem called Maximum Planar Triangles (MPT). We show that this problem is NP-hard and quantify how good an approximation algorithm for MPT performs as an approximation for MPS. We give a greedy 1/11-approximation algorithm for Mpt and show that the approximation ratio can be improved to 1/6 by using locally optimal triangular cactus subgraphs.

In dieser Dissertation zeigen wir, wie planare Teilgraphen mit speziellen Eigenschaften verwendet werden können, um effiziente Algorithmen für zwei NP-schwere Probleme in der kombinatorischen Optimierung zu fi nden. Im ersten Teil entwickeln wir Algorithmen zur Berechnung von Tutte-Wegen und zeigen, wie diese verwendet werden können, um lange Kreise und andere Lockerungen der Hamilton-Charakteristik zu finden, wenn wir uns auf Graphen in der Ebene beschränken. Wir beschreiben zunächst einen O(n^2)-Algorithmus in Circuit-Graphen und verallgemeinern diesen anschließend für die Berechnung von Tutte-Wegen in 2-zusammenhängenden planaren Graphen. Im zweiten Teil untersuchen wir das Maximum Planar Subgraph Problem (MPS) und zeigen, wie besonders dichte planare Teilgraphen verwendet werden können, um neue Approximationsalgorithmen zu entwickeln. Unsere Ergebnisse basieren auf einem neuartigen Ansatz, bei dem die Anzahl der dreieckigen Gebiete im berechneten Teilgraphen maximiert wird. Dazu de finieren wir ein neues Optimierungsproblem namens Maximum Planar Triangles (MPT). Wir zeigen, dass dieses Problem NP-schwer ist und quantifi zieren, wie gut ein Approximationsalgorithmus für MPT als Approximation für MPS funktioniert. Wir geben einen 1/11-Approximationsalgorithmus für MPT und zeigen, wie dies durch die Verwendung von lokal optimaler Kaktus-Teilgraphen auf 1/6 verbessert werden kann.