Counting crossing-free structures

DOI10.1145/2261250.2261259MaRDI QIDQ2874565zbMATH OpenOpenAlexFDO

Authors Karl Bringmann, Radu Curticapean, Saurabh Ray, Victor Alvarez

Publication date 7 August 2014

Published in Proceedings of the twenty-eighth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2261250.2261259

zbMATH Keywords

triangulationscountingparameterized complexityonion layers

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• Counting triangulations and other crossing-free structures via onion layers
• Peeling and nibbling the cactus: subexponential-time algorithms for counting triangulations and related problems
• Counting and enumerating crossing-free geometric graphs
• Counting and enumerating crossing-free geometric graphs
• A QPTAS for the base of the number of crossing-free structures on a planar point set

Cited in

(14)

• A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set
• From crossing-free graphs on wheel sets to embracing simplices and polytopes with few vertices
• Connecting the dots (with minimum crossings)
• Non-crossing Hamiltonian paths and cycles in output-polynomial time
• Non-crossing Hamiltonian paths and cycles in output-polynomial time
• Counting triangulations and other crossing-free structures via onion layers
• The Number of Crossing Free Configurations on Finite Point Sets in the Plane
• Counting and enumerating crossing-free geometric graphs
• Counting and enumerating crossing-free geometric graphs
• Convex polygons in geometric triangulations
• Parameterized analysis and crossing minimization problems
• A QPTAS for the base of the number of crossing-free structures on a planar point set
• Peeling and nibbling the cactus: subexponential-time algorithms for counting triangulations and related problems
• Counting triangulations and other crossing-free structures approximately

This page was built for publication: Counting crossing-free structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2874565)