Amortized efficiency of generating planar paths in convex position

DOI10.1016/j.tcs.2011.04.017zbMath1223.68088OpenAlexW1978034815MaRDI QIDQ638510

Yue-Li Wang, Ro-Yu Wu, Jou-Ming Chang, Kung-Jui Pai

Publication date: 12 September 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.04.017

zbMATH Keywords

geometric graphsconvex positionenumeration algorithmsamortized analysisgray codesplanar paths

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (2)

Reconstruction of the path graph ⋮ Transition operations over plane trees

Cites Work

• Unnamed Item
• Unnamed Item
• A quadratic distance bound on sliding between crossing-free spanning trees
• Flips in planar graphs
• Enumerating edge-constrained triangulations and edge-constrained non-crossing geometric spanning trees
• Planar tree transformation: results and counterexample
• On the diameter of geometric path graphs of points in convex position
• Transforming spanning trees: A lower bound
• Transforming spanning trees and pseudo-triangulations
• A technique for generating Gray codes
• Geometric tree graphs of points in convex position
• Balanced Gray codes
• Reverse search for enumeration
• Enumerating non-crossing minimally rigid frameworks
• On planar path transformation
• Gray code enumeration of plane straight-line graphs
• A Technique for Generating Specialized Gray Codes
• Efficient generation of the binary reflected gray code and its applications
• A Survey of Combinatorial Gray Codes
• Fast enumeration algorithms for non-crossing geometric graphs
• Hamilton cycles in the path graph of a set of points in convex position
• Sequences of spanning trees and a fixed tree theorem

This page was built for publication: Amortized efficiency of generating planar paths in convex position