{"id":"arxiv/2603.22262","url":"https://arxiv.org/abs/2603.22262","tags":["cs.CG","math.CO"],"score":0,"title":"Flip Distance of Non-Crossing Spanning Trees: NP-Hardness and Improved Bounds","domain":"cs.CG","source":"arxiv","authors":["Håvard Bakke Bjerkevik","Joseph Dorfer","Linda Kleist","Torsten Ueckerdt","Birgit Vogtenhuber"],"reviews":0,"subject":"cs.CG","summary":"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 for each non-crossing spanning tree on $P$ and an edge between any two spanning trees that can be transformed into each other by the exchange of a single edge. This flip graph has been intensively studied, lately with an emphasis on determining its diameter diam$(F(P))$ for sets $P$ of $n$ points in convex position. The current best bounds are $\\frac{14}{9}n-O(1) \\leq$ diam$(F(P))<\\frac{15}{9}n-3$ [Bjerkevik,…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-03-23","reactions":{}}