Counting and enumerating crossing-free geometric graphs

DOI10.20382/JOCG.V8I1A4zbMATH Open1393.68178arXiv1604.05350OpenAlexW2611197709MaRDI QIDQ5745385FDOQ5745385

Authors: Manuel Wettstein 

Publication date: 5 June 2018

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.

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

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

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)

Cited In (20)

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

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)