Match-And-Merge: A New Greedy Framework for Maximum Planar Subgraphs

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.