2026-07-23T21:02:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5944 2024-03-06T10:37:20Z ddc:004 open_access

Peeling and Nibbling the Cactus: Subexponential-Time Algorithms for Counting Triangulations and Related Problems Marx, Dániel Miltzow, Tillmann computational geometry triangulations exponential-time algorithms Given a set of n points S in the plane, a triangulation T of S is a maximal set of non-crossing segments with endpoints in S. We present an algorithm that computes the number of triangulations on a given set of n points in time n^{ (11+ o(1)) sqrt{n} }, significantly improving the previous best running time of O(2^n n^2) by Alvarez and Seidel [SoCG 2013]. Our main tool is identifying separators of size O(sqrt{n}) of a triangulation in a canonical way. The definition of the separators are based on the decomposition of the triangulation into nested layers ("cactus graphs"). Based on the above algorithm, we develop a simple and formal framework to count other non-crossing straight-line graphs in n^{O(sqrt{n})} time. We demonstrate the usefulness of the framework by applying it to counting non-crossing Hamilton cycles, spanning trees, perfect matchings, 3-colorable triangulations, connected graphs, cycle decompositions, quadrangulations, 3-regular graphs, and more. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dániel Marx and Tillmann Miltzow 2016 Is Part Of LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2016.52 urn:nbn:de:0030-drops-59445 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.52 eng https://creativecommons.org/licenses/by/3.0/legalcode