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