Counting polygon triangulations is hard
From MaRDI portal
Publication:2223620
DOI10.1007/s00454-020-00251-7zbMath1460.52022arXiv1903.04737OpenAlexW3096901045MaRDI QIDQ2223620
Publication date: 29 January 2021
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1903.04737
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial complexity of geometric structures (52C45)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Counting triangulations of planar point sets
- The complexity of computing the permanent
- How to draw a planar graph on a grid
- Note on the number of triangulations of planar point sets
- Analytic combinatorics of non-crossing configurations
- Triangulating planar graphs while minimizing the maximum degree
- An upper bound for the number of planar lattice triangulations
- Lower bounds on the number of crossing-free subgraphs of \(K_N\)
- A QPTAS for the base of the number of crossing-free structures on a planar point set
- Point sets with many non-crossing perfect matchings
- Flipping edges in triangulations
- An efficient algorithm for enumeration of triangulations
- A better upper bound on the number of triangulations of a planar point set
- A lower bound on the number of triangulations of planar point sets
- Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique
- Counting triangulations and other crossing-free structures approximately
- Counting triangulations and other crossing-free structures via onion layers
- On the number of plane geometric graphs
- Computational complexity of counting problems on 3-regular planar graphs
- On the number of pseudo-triangulations of certain point sets
- The Complexity of Counting in Sparse, Regular, and Planar Graphs
- Bounds on the Maximum Multiplicity of Some Common Geometric Graphs
- An improved lower bound on the minimum number of triangulations
- Peeling and Nibbling the Cactus: Subexponential-Time Algorithms for Counting Triangulations and Related Problems
- On the Number of Crossing‐Free Matchings, Cycles, and Partitions
- Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm
- On counting homomorphisms to directed acyclic graphs
- Hard Enumeration Problems in Geometry and Combinatorics
- Forbidden Configurations in Discrete Geometry
- On the computational complexity of the Jones and Tutte polynomials
- Generating triangulations at random
- Every planar graph is the intersection graph of segments in the plane
- A simple aggregative algorithm for counting triangulations of planar point sets and related problems
- Stochastic Minimum Spanning Trees and Related Problems
- Computing and Combinatorics
- Counting and enumerating crossing-free geometric graphs
This page was built for publication: Counting polygon triangulations is hard
