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

spanning treestriangulationsperfect matchingscountingcrossing-free geometric graphsenumeratingconvex partitionsconvex subdivisionsspanning cycles

Mathematics Subject Classification ID

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) Enumeration in graph theory (05C30) Graph representations (geometric and intersection representations, etc.) (05C62)

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)

• 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 plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique
• 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
• A QPTAS for the base of the number of crossing-free structures on a planar point set
• Counting and enumerating crossing-free geometric graphs
• Convex polygons in geometric triangulations
• Enumerating edge-constrained triangulations and edge-constrained non-crossing geometric spanning trees
• Number of crossing-free geometric graphs vs. Triangulations
• Counting triangulations and other crossing-free structures approximately
• Loopless Gray code enumeration and the Tower of Bucharest
• Faradžev Read-type enumeration of non-isomorphic CC systems
• 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
• Parameterized analysis and crossing minimization problems
• Crossing-free perfect matchings in wheel point sets
• Fast enumeration algorithms for non-crossing geometric graphs
• The Number of Crossing Free Configurations on Finite Point Sets in the Plane
• Enumeration of bipartite non-crossing geometric graphs
• Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique
• 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 Q4635522)