The rotation distance of brooms

Abstract

The associahedron $\mathcal{A}(G)$ of a graph $G$ has the property that its vertices can be thought of as the search trees on $G$ and its edges as the rotations between two search trees. If $G$ is a simple path, then $\mathcal{A}(G)$ is the usual associahedron and the search trees on $G$ are binary search trees. Computing distances in the graph of $\mathcal{A}(G)$, or equivalently, the rotation distance between two binary search trees, is a major open problem. Here, we consider the different case when $G$ is a complete split graph. In that case, $\mathcal{A}(G)$ interpolates between the stellohedron and the permutohedron, and all the search trees on $G$ are brooms. We show that the rotation distance between any two such brooms and therefore the distance between any two vertices in the graph of the associahedron of $G$ can be computed in quasi-quadratic time in the number of vertices of $G$.

arXiv comment26 pages, 3 figures

References in corpus (10)

• The diameter of associahedra
• Many non-equivalent realizations of the associahedron
• Flip Distance Between Triangulations of a Simple Polygon is NP-Complete
• Flip Distance Between Triangulations of a Planar Point Set is APX-Hard
• The diameter of type D associahedra and the non-leaving-face property
• The asymptotic diameter of cyclohedra
• Diameter estimates for graph associahedra
• Edge conflicts do not determine geodesics in the associahedron
• Strong convexity in flip-graphs
• Combinatorial generation via permutation languages. IV. Elimination trees