Abstract
Let S be a planar point set in general position, and let P(S) be the set of all plane (straight-line)
spanning paths for S. A flip in a path P ∈ P(S) is the operation of removing an edge e ∈ P and
replacing it with a new edge f on S such that the resulting graph is again a path in P(S). Towards
the question whether any two plane spanning paths of P(S) can be transformed into each other by
a sequence of flips, we give positive answers if S is a wheel set, an ice cream cone, or a double chain.
On the other hand, we show that in the general setting, it is sufficient to prove the statement for
plane spanning paths with fixed first edge.
spanning paths for S. A flip in a path P ∈ P(S) is the operation of removing an edge e ∈ P and
replacing it with a new edge f on S such that the resulting graph is again a path in P(S). Towards
the question whether any two plane spanning paths of P(S) can be transformed into each other by
a sequence of flips, we give positive answers if S is a wheel set, an ice cream cone, or a double chain.
On the other hand, we show that in the general setting, it is sufficient to prove the statement for
plane spanning paths with fixed first edge.
| Original language | English |
|---|---|
| Title of host publication | 38th European Workshop on Computational Geometry, Perugia, Italy, March 14–16, 2022 |
| Pages | 1-7 |
| Publication status | Published - 2022 |
Keywords
- CG
- GRAPH