Shelling and Sinking Graphs on the Sphere

We describe a promising approach to efficiently morph spherical graphs, extending earlier approaches of Awartani and Henderson [Trans.AMS 1987] and Kobourov and Landis [JGAA 2006]. Specifically, we describe two methods to morph shortest-path triangulations of the sphere by moving their vertices along longitudes into the southern hemisphere; we call a triangulation sinkable if such a morph exists. Our first method generalizes a longitudinal shelling construction of Awartani and Henderson; a triangulation is sinkable if a specific orientation of its dual graph is acyclic. We describe a simple polynomial-time algorithm to find a longitudinally shellable rotation of a given spherical triangulation, if one exists; we also construct a spherical triangulation that has no longitudinally shellable rotation. Our second method is based on a linear-programming characterization of sinkability. By identifying its optimal basis, we show that this linear program can be solved in $O(n^{\omega/2})$ time, where $\omega$ is the matrix-multiplication exponent, assuming the underlying linear system is non-singular. Finally, we pose several conjectures and describe experimental results that support them.

Shelling and sinking graphs on the sphere