Chalermsook, Parinya ;
Schmid, Andreas ;
Uniyal, Sumedha
A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs
Abstract
A cactus graph is a graph in which any two cycles are edgedisjoint. We present a constructive proof of the fact that any plane graph G contains a cactus subgraph C where C contains at least a 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 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 1/11approximation; (ii) An alternate (and arguably more illustrative) proof of the 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.
BibTeX  Entry
@InProceedings{chalermsook_et_al:LIPIcs:2019:10258,
author = {Parinya Chalermsook and Andreas Schmid and Sumedha Uniyal},
title = {{A Tight Extremal Bound on the Lov{\'a}sz Cactus Number in Planar Graphs}},
booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
pages = {19:119:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771009},
ISSN = {18688969},
year = {2019},
volume = {126},
editor = {Rolf Niedermeier and Christophe Paul},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10258},
doi = {10.4230/LIPIcs.STACS.2019.19},
annote = {Keywords: Graph Drawing, Matroid Matching, Maximum Planar Subgraph, Local Search Algorithms}
}
2019
Keywords: 

Graph Drawing, Matroid Matching, Maximum Planar Subgraph, Local Search Algorithms 
Seminar: 

36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Issue date: 

2019 
Date of publication: 

2019 