max planck institut
informatik

# MPI-INF or MPI-SWS or Local Campus Event Calendar

 << Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
Title: Match-And-Merge: A New Greedy Framework for Maximum Planar Subgraphs Andreas Schmid MMCI; AG1 Mittagsseminar (own work) D1, D2, D3, D4, D5, RG1, SWS, MMCIWe use this to send out email in the morning. AG Audience English
Date: Tuesday, 1 March 2016 13:00 30 Minutes Saarbrücken E1 4 024
 In this paper, we study two closely related combinatorial optimization problems on planar graphs. In the first problem, we are given a graph G, and Maximum Planar Subgraph (MPS) asks for a planar subgraph of G that contains the maximum number of edges. MPS has many applications including, for instance, circuit design, factory layout, and graph drawing, so it has received a lot of attention from both theoretical and empirical literature. Since the problem is NP-hard, past theoretical research has focused on approximation algorithms. The current best known approximation ratio is 4/9 obtained two decades ago (Calinescu et al. SODA 1996) based on computing as many edge-disjoint triangles in an input graph as possible. They also showed that 4/9 is provably the limit of the disjoint triangles approach. This motivates us to formulate and study our second problem: In Maximum Planar Triangles (MPT), we are interested in computing a subgraph that admits a planar embedding with as many triangular faces as possible. We show that this problem is NP-hard and precisely quantify the connection between the two problems: For $\beta <1$, a $\beta$-approximation for MPT gives a min(1/3 + (2 \beta} /3), 1/2)-approximation for MPS, so this approach allows potentially up to a 1/2-approximation for MPS, provided the existence of a 1/4-approximation for MPT. We show a simple greedy algorithm that achieves a 1/11-approximation for MPT and 13/33 for MPS respectively. Key to our result is a greedy strategy that iteratively finds diamond subgraphs in an input graph. While our approximation ratio for MPS is below 4/9, our algorithm is simple, easy to implement, and strictly better than previously proposed greedy algorithms which, we show, can never be better than 7/18.
Name(s): Andreas Schmid