Fast enumeration algorithms for non-crossing geometric graphs
From MaRDI portal
Publication:5896957
DOI10.1007/s00454-009-9164-4zbMath1177.05119OpenAlexW4233537290MaRDI QIDQ5896957
Naoki Katoh, Shin-ichi Tanigawa
Publication date: 27 August 2009
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00454-009-9164-4
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Enumeration in graph theory (05C30) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (4)
An upper bound for the number of rectangulations of a planar point set ⋮ Amortized efficiency of generating planar paths in convex position ⋮ Counting triangulations and other crossing-free structures approximately ⋮ Counting triangulations and other crossing-free structures via onion layers
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A quadratic distance bound on sliding between crossing-free spanning trees
- Enumerating constrained non-crossing minimally rigid frameworks
- Enumerating edge-constrained triangulations and edge-constrained non-crossing geometric spanning trees
- Transforming spanning trees and pseudo-triangulations
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- Triangulating a simple polygon in linear time
- On the finiteness of the criss-cross method
- A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
- Analytic combinatorics of non-crossing configurations
- The complexity of detecting crossingfree configurations in the plane
- Enumerating pseudo-triangulations in the plane
- Flipping edges in triangulations
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- An efficient algorithm for enumeration of triangulations
- Graphs of non-crossing perfect matchings
- Reverse search for enumeration
- An algorithm for enumerating all spanning trees of a directed graph
- On the number of plane geometric graphs
- Enumerating non-crossing minimally rigid frameworks
- Gray code enumeration of plane straight-line graphs
- Pebble game algorithms and sparse graphs
- Graphs of triangulations and perfect matchings
- Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm
- An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs
- A Survey of Combinatorial Gray Codes
- Algorithms for Enumerating All Spanning Trees of Undirected and Weighted Graphs
- EFFICIENTLY SCANNING ALL SPANNING TREES OF AN UNDIRECTED GRAPH
- Algorithms - ESA 2003
- Sequences of spanning trees and a fixed tree theorem
This page was built for publication: Fast enumeration algorithms for non-crossing geometric graphs
