A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussavertaisarvioitu

Standard

A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs. / Chalermsook, Parinya; Schmid, Andreas; Uniyal, Sumedha.

36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2019. s. 1-14 19 (Leibniz international proceedings in informatics; Vuosikerta 126).

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussavertaisarvioitu

Harvard

Chalermsook, P, Schmid, A & Uniyal, S 2019, A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs. julkaisussa 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)., 19, Leibniz international proceedings in informatics, Vuosikerta. 126, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Sivut 1-14, Symposium on Theoretical Aspects of Computer Science, Berlin, Saksa, 13/03/2019. https://doi.org/10.4230/LIPIcs.STACS.2019.19

APA

Chalermsook, P., Schmid, A., & Uniyal, S. (2019). A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs. teoksessa 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) (Sivut 1-14). [19] (Leibniz international proceedings in informatics; Vuosikerta 126). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.STACS.2019.19

Vancouver

Chalermsook P, Schmid A, Uniyal S. A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs. julkaisussa 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2019. s. 1-14. 19. (Leibniz international proceedings in informatics). https://doi.org/10.4230/LIPIcs.STACS.2019.19

Author

Chalermsook, Parinya ; Schmid, Andreas ; Uniyal, Sumedha. / A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs. 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2019. Sivut 1-14 (Leibniz international proceedings in informatics).

Bibtex - Lataa

@inproceedings{f4741194300d4e769ed6d89ddc3617e9,
title = "A Tight Extremal Bound on the Lov{\'a}sz Cactus Number in Planar Graphs",
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 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/11-approximation; (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.",
author = "Parinya Chalermsook and Andreas Schmid and Sumedha Uniyal",
year = "2019",
doi = "10.4230/LIPIcs.STACS.2019.19",
language = "English",
series = "Leibniz international proceedings in informatics",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
pages = "1--14",
booktitle = "36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)",
address = "Germany",

}

RIS - Lataa

TY - GEN

T1 - A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs

AU - Chalermsook, Parinya

AU - Schmid, Andreas

AU - Uniyal, Sumedha

PY - 2019

Y1 - 2019

N2 - 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 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/11-approximation; (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.

AB - 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 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/11-approximation; (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.

U2 - 10.4230/LIPIcs.STACS.2019.19

DO - 10.4230/LIPIcs.STACS.2019.19

M3 - Conference contribution

T3 - Leibniz international proceedings in informatics

SP - 1

EP - 14

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

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

ER -

ID: 40353265