Sparse Outerstring Graphs Have Logarithmic Treewidth
<|reference_start|>Sparse Outerstring Graphs Have Logarithmic Treewidth: An outerstring graph is the intersection graph of curves lying inside a disk with one endpoint on the boundary of the disk. We show that an outerstring graph with $n$ vertices has treewidth $O(\alpha\log n)$, where $\alpha$ denotes the arboricity of the graph, with an almost matching lower bound of $\Omega(\alpha \log (n/\alpha))$. As a corollary, we show that a $t$-biclique-free outerstring graph has treewidth $O(t(\log t)\log n)$. This leads to polynomial-time algorithms for most of the central NP-complete problems such as \textsc{Independent Set}, \textsc{Vertex Cover}, \textsc{Dominating Set}, \textsc{Feedback Vertex Set}, \textsc{Coloring} for sparse outerstring graphs. Also, we can obtain subexponential-time (exact, parameterized, and approximation) algorithms for various NP-complete problems such as \textsc{Vertex Cover}, \textsc{Feedback Vertex Set} and \textsc{Cycle Packing} for (not necessarily sparse) outerstring graphs.<|reference_end|>
@article{an2024sparse,
    title={Sparse Outerstring Graphs Have Logarithmic Treewidth},
    author={Shinwoo An, Eunjin Oh and Jie Xue},
    journal={arXiv preprint arXiv:2406.17424},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.17424},
    primaryClass={cs.CG cs.DS}
}