Amortized efficiency of generating planar paths in convex position

DOI10.1016/J.TCS.2011.04.017MaRDI QIDQ638510zbMATH OpenOpenAlexFDO

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

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 graphsenumeration algorithmsamortized analysisgray codesconvex positionplanar paths

Mathematics Subject Classification ID

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

Recommendations

• On planar path transformation
• Enumerating triangulation paths
• Listing All Plane Graphs
• Gray code enumeration of plane straight-line graphs
• Enumerating pseudo-triangulations in the plane

Cites work

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

Cited in

(4)

• On planar path transformation
• Non-crossing Hamiltonian paths and cycles in output-polynomial time
• Reconstruction of the path graph
• A tight amortized bound for path reversal

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q638510)