On the diameter of geometric path graphs of points in convex position

DOI10.1016/J.IPL.2008.12.017MaRDI QIDQ976134zbMATH OpenOpenAlexFDO

Authors Jou-Ming Chang, Ro-Yu Wu

Publication date 16 June 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2008.12.017

zbMATH Keywords

combinatorial problemsdiameterflipgeometric path graphplane spanning path

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Hamilton cycles in the path graph of a set of points in convex position
• Geometric tree graphs of points in convex position
• Reconstruction of the path graph
• On the connectedness and diameter of a geometric Johnson graph
• scientific article; zbMATH DE number 1332354

Cites work

• A quadratic distance bound on sliding between crossing-free spanning trees
• Distances between graphs under edge operations
• Flips in planar graphs
• Geometric tree graphs of points in convex position
• Hamilton cycles in the path graph of a set of points in convex position
• Lower bounds on the number of crossing-free subgraphs of \(K_N\)
• On planar path transformation
• Planar tree transformation: results and counterexample
• Reverse search for enumeration
• Sequences of spanning trees and a fixed tree theorem

Cited in

(9)

• Reconstruction of the path graph
• On the connectedness and diameter of a geometric Johnson graph
• Hamilton cycles in the path graph of a set of points in convex position
• Flipping plane spanning paths
• Amortized efficiency of generating planar paths in convex position
• Short flip sequences to untangle segments in the plane
• A linear time algorithm for the flip distance between plane spanning paths in convex point sets
• On the connectivity of the flip graph of plane spanning paths
• Reconfigurations of plane caterpillars and paths (poster abstract)

This page was built for publication: On the diameter of geometric path graphs of points in convex position

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