English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

A cactus graph is a graph in which any two cycles are edge-disjoint. Wepresent a constructive proof of the fact that any plane graph $G$ contains acactus subgraph $C$ where $C$ contains at least a $\frac{1}{6}$ fraction of thetriangular faces of $G$. We also show that this ratio cannot be improved byshowing a tight lower bound. Together with an algorithm for linear matroidparity, our bound implies two approximation algorithms for computing "denseplanar structures" inside any graph: (i) A $\frac{1}{6}$ approximationalgorithm for, given any graph $G$, finding a planar subgraph with a maximumnumber of triangular faces; this improves upon the previous$\frac{1}{11}$-approximation; (ii) An alternate (and arguably moreillustrative) proof of the $\frac{4}{9}$ approximation algorithm for finding aplanar subgraph with a maximum number of edges.  Our bound is obtained by analyzing a natural local search strategy andheavily exploiting the exchange arguments. Therefore, this suggests the powerof local search in handling problems of this kind.

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