Flipping plane spanning paths

DOI10.1007/978-3-031-27051-2_5MaRDI QIDQ6091145zbMATH OpenFDO

Authors Oswin Aichholzer, Kristin Knorr, Wolfgang Mulzer, Johannes Obenaus, Rosna Paul, Birgit Vogtenhuber

Publication date 24 November 2023

Published in WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2202.10831

zbMATH Keywords

flipsgeneralized double circlesplane spanning paths

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: Let $S$ be a planar point set in general position, and let $mathcalP(S)$ be the set of all plane straight-line paths with vertex set $S$. A flip on a path $PinmathcalP(S)$ is the operation of replacing an edge $e$ of $P$ with another edge $f$ on $S$ to obtain a new valid path from $mathcalP(S)$. It is a long-standing open question whether for every given point set $S$, every path from $mathcalP(S)$ can be transformed into any other path from $mathcalP(S)$ by a sequence of flips. To achieve a better understanding of this question, we show that it is sufficient to prove the statement for plane spanning paths whose first edge is fixed. Furthermore, we provide positive answers for special classes of point sets, namely, for wheel sets and generalized double circles (which include, e.g., double chains and double circles).

Cites work

• Enumerating order types for small point sets with applications
• Flips in planar graphs
• Graphs of non-crossing perfect matchings
• Graphs of triangulations and perfect matchings
• Introduction to reconfiguration
• On planar path transformation
• On the diameter of geometric path graphs of points in convex position
• Transforming triangulations

Cited in

(4)

• A linear time algorithm for the flip distance between plane spanning paths in convex point sets
• Flips in odd matchings
• 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: Flipping plane spanning paths

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