Counting and enumerating crossing-free geometric graphs

DOI10.1145/2582112.2582145MaRDI QIDQ4635522zbMATH OpenOpenAlexFDO

Authors Manuel Wettstein

Publication date 23 April 2018

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

Full work available at URL http://hdl.handle.net/20.500.11850/314615

zbMATH Keywords

convex partitionsconvex subdivisionscountingcrossing-free geometric graphsenumeratingperfect matchingsspanning cyclesspanning treestriangulations

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

(25)

• Loopless Gray code enumeration and the Tower of Bucharest
• A QPTAS for the base of the number of crossing-free structures on a planar point set
• Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique
• Enumeration of bipartite non-crossing geometric graphs
• Parameterized analysis and crossing minimization problems
• Counting the number of crossings in geometric graphs
• Faradžev Read-type enumeration of non-isomorphic CC systems
• Counting triangulations and other crossing-free structures approximately
• Counting triangulations and other crossing-free structures via onion layers
• Counting crossing-free structures
• Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique
• Counting plane graphs with exponential speed-up
• Peeling and nibbling the cactus: subexponential-time algorithms for counting triangulations and related problems
• A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set
• Convex polygons in geometric triangulations
• Reporting the crossing-free segments of a complete geometric graph
• From crossing-free graphs on wheel sets to embracing simplices and polytopes with few vertices
• Crossing-free perfect matchings in wheel point sets
• Counting Plane Graphs: Cross-Graph Charging Schemes
• 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
• Fast enumeration algorithms for non-crossing geometric graphs
• On crossing numbers of geometric proximity graphs
• Enumerating edge-constrained triangulations and edge-constrained non-crossing geometric spanning trees

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