A Tight Extremal Bound on the Lov\'{a}sz Cactus Number in Planar Graphs

DOI10.4230/LIPICS.STACS.2019.19MaRDI QIDQ6300172arXivFDO

Authors Parinya Chalermsook, Andreas Schmid, Sumedha Uniyal

Publication date 10 April 2018

Published in arXiv

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2019.19

Mathematics Subject Classification ID

Theory of computing (68Qxx)

arXiv classification

cs.DMcs.DSmath.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 $frac16$ 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 $frac16$ approximation algorithm for, given any graph $G$, finding a planar subgraph with a maximum number of triangular faces; this improves upon the previous $frac111$-approximation; (ii) An alternate (and arguably more illustrative) proof of the $frac49$ 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.

This page was built for publication: A Tight Extremal Bound on the Lov\'{a}sz Cactus Number in Planar Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6300172)