Counting and enumerating crossing-free geometric graphs

DOI10.20382/JOCG.V8I1A4MaRDI QIDQ5745385zbMATH OpenOpenAlexFDO

Authors Manuel Wettstein

Publication date 5 June 2018

Full work available at URL https://arxiv.org/abs/1604.05350

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: We describe a framework for counting and enumerating various types of crossing-free geometric graphs on a planar point set. The framework generalizes ideas of Alvarez and Seidel, who used them to count triangulations in time $O(2^n{n}^2)$ where $n$ is the number of points. The main idea is to reduce the problem of counting geometric graphs to counting source-sink paths in a directed acyclic graph. The following new results will emerge. The number of all crossing-free geometric graphs can be computed in time $O(c^n{n}^4)$ for some $c<2.83929$. The number of crossing-free convex partitions can be computed in time $O(2^n{n}^4)$. The number of crossing-free perfect matchings can be computed in time $O(2^n{n}^4)$. The number of convex subdivisions can be computed in time $O(2^n{n}^4)$. The number of crossing-free spanning trees can be computed in time $O(c^n{n}^4)$ for some $c<7.04313$. The number of crossing-free spanning cycles can be computed in time $O(c^n{n}^4)$ for some $c<5.61804$. With the same bounds on the running time we can construct data structures which allow fast enumeration of the respective classes. For example, after $O(2^n{n}^4)$ time of preprocessing we can enumerate the set of all crossing-free perfect matchings using polynomial time per enumerated object. For crossing-free perfect matchings and convex partitions we further obtain enumeration algorithms where the time delay for each (in particular, the first) output is bounded by a polynomial in $n$. All described algorithms are comparatively simple, both in terms of their analysis and implementation.

Recommendations

• Counting and enumerating crossing-free geometric graphs
• Counting plane graphs with exponential speed-up
• Fast enumeration algorithms for non-crossing geometric graphs
• Counting crossing-free structures
• The Number of Crossing Free Configurations on Finite Point Sets in the Plane

Cited in

(20)

• From crossing-free graphs on wheel sets to embracing simplices and polytopes with few vertices
• Counting plane graphs with exponential speed-up
• Counting crossing-free structures
• On crossing numbers of geometric proximity graphs
• Counting the number of crossings in geometric graphs
• Reporting the crossing-free segments of a complete geometric graph
• Counting Plane Graphs: Cross-Graph Charging Schemes
• Counting and enumerating crossing-free geometric graphs
• Algorithmic enumeration of surrounding polygons
• Enumerating edge-constrained triangulations and edge-constrained non-crossing geometric spanning trees
• Non-crossing Hamiltonian paths and cycles in output-polynomial time
• Number of crossing-free geometric graphs vs. Triangulations
• Counting triangulations and other crossing-free structures approximately
• Counting polygon triangulations is hard
• Connecting the dots (with minimum crossings)
• Fast enumeration algorithms for non-crossing geometric graphs
• scientific article; zbMATH DE number 7559233 (Why is no real title available?)
• The Number of Crossing Free Configurations on Finite Point Sets in the Plane
• On crossing families of complete geometric graphs
• Counting triangulations and other crossing-free structures via onion layers

This page was built for publication: Counting and enumerating crossing-free geometric graphs

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