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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Given a set of $n$ points $S$ in the plane, a triangulation $T$ of $S$ is amaximal set of non-crossing segments with endpoints in $S$. We present analgorithm that computes the number of triangulations on a given set of $n$points in time $n^{(11+ o(1))\sqrt{n} }$, significantly improving the previousbest running time of $O(2^n n^2)$ by Alvarez and Seidel [SoCG 2013]. Our maintool is identifying separators of size $O(\sqrt{n})$ of a triangulation in acanonical way. The definition of the separators are based on the decompositionof the triangulation into nested layers ("cactus graphs"). Based on the abovealgorithm, we develop a simple and formal framework to count other non-crossingstraight-line graphs in $n^{O(\sqrt{n})}$ time. We demonstrate the usefulnessof the framework by applying it to counting non-crossing Hamilton cycles,spanning trees, perfect matchings, $3$-colorable triangulations, connectedgraphs, cycle decompositions, quadrangulations, $3$-regular graphs, and more.

Peeling and Nibbling the Cactus: Subexponential-Time Algorithms for Counting Triangulations and Related Problems