Counting plane graphs with exponential speed-up

DOI10.1007/978-3-642-19391-0_3MaRDI QIDQ3003469zbMATH OpenOpenAlexFDO

Authors Andreas Razen, Emo Welzl

Publication date 27 May 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-19391-0_3

zbMATH Keywords

constrained Delaunay triangulationcountingcrossing-free configurationsedge flipsplane graphstriangulations

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Counting and enumerating crossing-free geometric graphs
• Counting and enumerating crossing-free geometric graphs
• Number of crossing-free geometric graphs vs. Triangulations

Cites work

• A better upper bound on the number of triangulations of a planar point set
• An efficient algorithm for enumeration of triangulations
• Analytic combinatorics of non-crossing configurations
• Counting triangulations of planar point sets
• Crossing-Free Subgraphs
• Fast enumeration algorithms for non-crossing geometric graphs
• Generalized Delaunay triangulation for planar graphs
• scientific article; zbMATH DE number 5506218 (Why is no real title available?)
• On the Number of Crossing‐Free Matchings, Cycles, and Partitions
• On the number of plane geometric graphs
• Reverse search for enumeration

Cited in

(11)

• Counting triangulations and other crossing-free structures approximately
• Counting triangulations and other crossing-free structures via onion layers
• Peeling and nibbling the cactus: subexponential-time algorithms for counting triangulations and related problems
• Convex polygons in geometric triangulations
• Counting and enumerating crossing-free geometric graphs
• Number of crossing-free geometric graphs vs. Triangulations
• The Number of Crossing Free Configurations on Finite Point Sets in the Plane
• Counting and enumerating crossing-free geometric graphs
• Non-crossing Hamiltonian paths and cycles in output-polynomial time
• Upward pointset embeddings of planar st-graphs
• Upward pointset embeddings of planar \(st\)-graphs

This page was built for publication: Counting plane graphs with exponential speed-up

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