Enumerating edge-constrained triangulations and edge-constrained non-crossing geometric spanning trees
From MaRDI portal
Publication:967420
DOI10.1016/j.dam.2009.04.019zbMath1227.05236OpenAlexW2122233371MaRDI QIDQ967420
Naoki Katoh, Shin-ichi Tanigawa
Publication date: 28 April 2010
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/2433/123380
Trees (05C05) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Amortized efficiency of generating planar paths in convex position, Fast enumeration algorithms for non-crossing geometric graphs, Algorithmic enumeration of surrounding polygons
Cites Work
- Unnamed Item
- Unnamed Item
- A quadratic distance bound on sliding between crossing-free spanning trees
- Enumerating constrained non-crossing minimally rigid frameworks
- Transforming spanning trees and pseudo-triangulations
- Corrections to Lee's visibility polygon algorithm
- A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
- The complexity of detecting crossingfree configurations in the plane
- Enumerating pseudo-triangulations in the plane
- Flipping edges in triangulations
- On local transformation of polygons with visibility properties.
- An efficient algorithm for enumeration of triangulations
- Graphs of non-crossing perfect matchings
- Reverse search for enumeration
- On the number of plane geometric graphs
- Gray code enumeration of plane straight-line graphs
- An efficient algorithm for determining the convex hull of a finite planar set
- Graphs of triangulations and perfect matchings
- Visibility of a simple polygon
- Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm
- Fast enumeration algorithms for non-crossing geometric graphs
- Sequences of spanning trees and a fixed tree theorem