Flip Distance of Non-Crossing Spanning Trees: NP-Hardness and Improved Bounds

Håvard Bakke Bjerkevik, Joseph Dorfer, Linda Kleist +2

We consider the problem of reconfiguring non-crossing spanning trees on point sets. For a set $P$ of $n$ points in general position in the plane, the flip graph $F(P)$ has a vertex…