Counting and Enumerating Crossing-free Geometric Graphs

DOI10.1145/2582112.2582145zbMath1395.68319OpenAlexW1994969571MaRDI QIDQ4635522

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

triangulationscountingperfect matchingsspanning treescrossing-free geometric graphsenumeratingconvex partitionsconvex subdivisionsspanning cycles

Mathematics Subject Classification ID

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 algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (8)

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 ⋮ Convex Polygons in Geometric Triangulations ⋮ Parameterized analysis and crossing minimization problems ⋮ A QPTAS for the base of the number of crossing-free structures on a planar point set ⋮ Crossing-Free Perfect Matchings in Wheel Point Sets ⋮ Counting triangulations and other crossing-free structures approximately ⋮ Counting triangulations and other crossing-free structures via onion layers

This page was built for publication: Counting and Enumerating Crossing-free Geometric Graphs