hide
Free keywords:
Computer Science, Discrete Mathematics, cs.DM,Computer Science, Data Structures and Algorithms, cs.DS,Mathematics, Combinatorics, math.CO
Abstract:
A cactus graph is a graph in which any two cycles are edge-disjoint. We
present a constructive proof of the fact that any plane graph $G$ contains a
cactus subgraph $C$ where $C$ contains at least a $\frac{1}{6}$ fraction of the
triangular faces of $G$. We also show that this ratio cannot be improved by
showing a tight lower bound. Together with an algorithm for linear matroid
parity, our bound implies two approximation algorithms for computing "dense
planar structures" inside any graph: (i) A $\frac{1}{6}$ approximation
algorithm for, given any graph $G$, finding a planar subgraph with a maximum
number of triangular faces; this improves upon the previous
$\frac{1}{11}$-approximation; (ii) An alternate (and arguably more
illustrative) proof of the $\frac{4}{9}$ approximation algorithm for finding a
planar subgraph with a maximum number of edges.
Our bound is obtained by analyzing a natural local search strategy and
heavily exploiting the exchange arguments. Therefore, this suggests the power
of local search in handling problems of this kind.
