Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

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)
What and Who
Title:Match-And-Merge: A New Greedy Framework for Maximum Planar Subgraphs
Speaker:Andreas Schmid
coming from:MMCI;
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 1 March 2016
Duration:30 Minutes
Building:E1 4
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
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Created:Andreas Schmid, 01/26/2016 09:43 AM Last modified:Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Andreas Schmid, 02/22/2016 02:20 PM
  • Christina Fries, 02/11/2016 10:21 AM
  • Andreas Schmid, 01/26/2016 09:43 AM -- Created document.