Shelling and Sinking Graphs on the Sphere

In light of the long history of results for morphing planar graphs and their generalizations to higher-genus surfaces, it is surprising how little is known about morphing graphs on the sphere. Although embeddings on the sphere are topologically equivalent to embeddings in the plane, the different geometries of the two surfaces induce significantly different behavior.

In 1944, Cairns [12] proved that any two isomorphic shortest-path triangulations of the sphere are connected by a continuous family of shortest-path triangulations, using essentially the same edge-contraction strategy that he used for planar triangulations (but with more complex case analysis). A direct translation of Cairns’s spherical morphing proof leads to an exponential-time algorithm; unlike his planar result, this is still the fastest algorithm known. In fact, as far as we are aware, this is the only algorithm known for morphing arbitrary spherical triangulations.

Morphing algorithms are known for a few special cases of spherical triangulations. Almost all of these algorithms operate by moving vertices along longitudes into the southern hemisphere, projecting the resulting “southern” triangulation into the plane, and applying a planar morphing algorithm. Awartani and Henderson [4] describe an algorithm to morph spherical triangulations that satisfy a certain longitudinal shelling condition using this strategy. They also prove that any triangulation with a longitudinal seam, meaning there is a longitude that does not cross the interior of any edge, satisfies their shelling condition. (We study Awartani and Henderson’s shelling condition in more detail in Section 3.) Kobourov and Landis [41] describe an algorithm to morph between Delaunay triangulations via longitudinal morphs; their algorithm easily generalizes to coherent triangulations, which are central projections of arbitrary convex polyhedra. The same method is also implicit in Richter-Gebert’s proof [47, Theorem 13.3.3] of classical theorems of Eberhard [21] and Steinitz [50] describing morphs between isomorphic convex polyhedra.

We call a sphere triangulation sinkable if it can be morphed along longitudes into the southern hemisphere. Every coherent triangulation is longitudinally shellable, and every longitudinally shellable triangulation is sinkable. Awartani and Henderson [4] describe an example of an unsinkable triangulation; it is not possible to move the vertices of their triangulation into the southern hemisphere without inverting at least one face. The simplest examples of unsinkable triangulation are the central projections of sufficiently twisted Schönhardt polyhedra [48], where the rotated faces are normal to the $z$-axis; see Figure 1.1. (Supnick proved that Schönhardt triangulations are the simplest non-coherent triangulations [54, 55]; our algorithm in Section 5 can be used to determine which of them are sinkable.)

The definitions of longitudinal shellability and sinkability depend on a specific choice of antipodal points as the north and south poles; neither property is invariant under rotations of the sphere. For example, a ${90}^{\circ }$ rotation around the $x$-axis makes every Schönhardt triangulation in Figure 1.1 longitudinally shellable, and therefore sinkable.

We describe a promising approach to efficiently morph shortest-path embeddings of graphs on the sphere, extending the previous results of Awartani and Henderson [4] and Kobourov and Landis [41]. At a high level, we propose finding suitable rotations of the sphere that allow the source and target embeddings to be pushed into the southern hemisphere along longitudes, thereby reducing to a planar morphing problem.

We emphasize that we do not develop this strategy into a complete algorithm; the existence of an efficient spherical morphing algorithm remains an open problem. We also note that sinking is not required to construct spherical morphs; for example, we can directly morph any Schönhardt triangulation into any other by twisting one face.

We begin in Section 2 by reviewing relevant definitions, describing our proposed morphing strategy in detail, and proving some preliminary results. In Section 3, we formally define the longitudinal shelling condition introduced by Awartani and Henderson and provide several combinatorial characterizations, each of which can be tested in $O(n)$ time. We also reiterate Awartani and Henderson’s proof that every longitudinally shellable triangulations is sinkable. In Section 4, we present an algorithm that either finds a rotation of a given sphere triangulation $\mathrm{\Gamma }$ that is longitudinally shellable, or reports correctly that no such rotation exists, in $O(n^{5/2}{\log }^{3}n)$ time. We also construct a spherical triangulation that has no longitudinally shellable rotation. In Section 5, we describe an efficient algorithm to determine whether a given sphere triangulation is sinkable. First we show that sinkability is equivalent to the feasibility of a certain linear program with $O(n)$ variables and constraints. By identifying the optimal basis for this linear program, we show that it can be solved in $O(n^{\omega /2})$ time, assuming the underlying linear system is non-singular.

Due to space constraints, we defer several proofs and related results to the full version [24]. In particular, we describe the results of lightweight experiments, which suggest that “in practice” one can find a shellable rotation of a spherical triangulation by testing a small number of random rotations. We also present several open problems for further research, including several conjectures suggested by our experimental results.

We consider drawings of graphs on the unit sphere $S^2=\{(x,y,z)\mid x^2+y^2+z^2=1\}$. The north pole is the point $(0,0,1)$; the south pole is the point $(0,0,-1)$; the equator is the intersection of the unit sphere with the plane $z=0$. A longitude is an open great-circular arc whose endpoints are the north and south poles. Every point except the poles lies on a unique longitude.

Throughout the paper, we fix an arbitrary simple maximal planar graph $G$ with $n\ge 4$ vertices, arbitrarily indexed from $1$ to $n$. An embedding of $G$ on the sphere is an injective map from $G$ to $S^2$, or less formally, a drawing of $G$ where edges are arbitrary simple curves that intersect only at their shared endpoints. Every embedding of $G$ on the sphere is a triangulation, meaning every face is bounded by a cycle of three distinct edges.

Unless explicitly indicated otherwise, we consider only generic shortest-path triangulations, meaning (1) every edge is a great-circular arc with length less than $\pi$; (2) no great circle contains more than two vertices, and (3) no great circle through the poles contains more than one vertex. Condition (1) is the natural spherical analogue of straight-line embeddings in the plane. Condition (3) implies that vertices lie on distinct longitudes.

Classical theorems of Steinitz [49, 50, 33] and Whitney [62, 8] imply that $G$ has a unique embedding on the sphere, up to homeomorphism, which is a generic shortest-path triangulation. A face of $G$ is a face of this essentially unique embedding. We sometimes identify each face as a triple $(i,j,k)$ of vertices (or their indices) in counterclockwise order around its interior.

Every generic shortest-path triangulation has a unique north face whose interior contains the north pole and a unique south face whose interior contains the south pole. The remaining non-polar faces are of two types: An up-face has one vertex (called its apex) directly north of its opposite edge (called its base); symmetrically, a down-face has one vertex (its apex) directly south of its opposite edge (its base). The legs of a non-polar face $f$ are the edges of $f$ incident to the apex of $f$. The faces immediately north and south of any vertex $i$ are respectively denoted ${𝒇}_{\text{above}}\mathbf{(}𝒊\mathbf{)}$ and ${𝒇}_{\text{below}}\mathbf{(}𝒊\mathbf{)}$. For each vertex $i$, $f_{\text{above}}(i)$ is either the north face or a down-face, and $f_{\text{below}}(i)$ is either the south face or an up-face. See Figure 2.1.

A face of a (generic) triangulation is everted if it has area greater than $2\pi$, or equivalently, if it contains an open hemisphere. Every triangulation contains at most one everted face. We call a triangulation full if no face is everted, and southern if every vertex lies below the equator (which implies that the north face is everted).

A connected region $R$ on the sphere is $𝜽$-monotone if every longitude is either disjoint from $R$ or has connected intersection with $R$.

Throughout the paper, we represent spherical triangulations implicitly as projections of certain polyhedra onto the unit sphere. Specifically, we represent each vertex using signed homogeneous coordinates [51, 52, 53] – for any scalar $\lambda >0$, the coordinate vectors $(x,y,z)$ and $(\lambda x,\lambda y,\lambda z)$ represent the same point on the sphere. We can freely rescale the vertices, each independently, without changing the underlying spherical triangulation; although it is never actually necessary, this rescaling is sometimes convenient for purposes of discussion and intuition. For example, we can implicitly interpret any southern triangulation as a planar triangulation by scaling vertices onto the tangent plane $z=-1$; this scaling is equivalent to the gnomonic or central projection $(x,y,z)\mapsto (-x/z,-y/z,-1)$. Awartani and Henderson [4] analyze longitudinal morphing (defined below) by implicitly scaling vertices onto the unit cylinder $x^2+y^2=1$.

Two embeddings ${\mathrm{\Gamma }}_0:G\to S^2$ and ${\mathrm{\Gamma }}_1:G\to S^2$ are isomorphic if they define the same rotation system, or equivalently, if there is an orientation-preserving homeomorphism $H:S^2\to S^2$ such that ${\mathrm{\Gamma }}_1=h\circ {\mathrm{\Gamma }}_0$. Two isomorphic embeddings are $𝜽$-equivalent if each vertex of $G$ lies on the same longitude in both embeddings.

A homotopy between two embeddings ${\mathrm{\Gamma }}_0:G\to S^2$ and ${\mathrm{\Gamma }}_1:G\to S^2$ is a continuous function $H:[0,1]\times G\to S^2$ such that $H(0,\cdot )={\mathrm{\Gamma }}_0$ and $H(1,\cdot )={\mathrm{\Gamma }}_1$. Any pair of isomorphic embeddings ${\mathrm{\Gamma }}_0$ and ${\mathrm{\Gamma }}_1$ are connected by an isotopy, which is a homotopy $H$ such that every intermediate drawing ${\mathrm{\Gamma }}_t=H(t,\cdot )$ is an embedding. (The edges of these intermediate embeddings can be arbitrary simple curves, not necessarily shortest paths.) A morph is an isotopy in which the edges of every intermediate embedding ${\mathrm{\Gamma }}_t$ are shortest paths. Finally, a longitudinal morph is a morph in which vertices move only along their longitudes.

Recall that a triangulation is sinkable if it can be longitudinally morphed to a $\theta$-equivalent triangulation with all vertices below the equator. A rotation of a spherical triangulation $\mathrm{\Gamma }$ is the triangulation $\rho \circ \mathrm{\Gamma }$ for some rigid motion $\rho :S^2\to S^2$ of the sphere.¹¹1Rotations should not be confused with rotation systems, which encodes the cyclic order of edges around each vertex in a planar or spherical embedding. Our strategy rests on the following (admittedly optimistic) conjecture:

Conjecture 2.4 implies that one can morph any triangulation ${\mathrm{\Gamma }}_0$ into any isotopic target triangulation ${\mathrm{\Gamma }}_1$ through an intermediate coherent triangulation ${\mathrm{\Gamma }}_{1/2}$. Steinitz’s theorem [49, 50, 33] implies that a coherent embedding ${\mathrm{\Gamma }}_{1/2}$ of $G$ exists. Given any coherent triangulation, we can project its underlying convex polyhedron from a point on the positive $z$-axis just outside the polyhedron to the plane $z=-1$, and then centrally project the resulting planar triangulation back to the southern hemisphere, to obtain a $\theta$-equivalent southern triangulation. It follows that every rotation of a coherent triangulation is sinkable.

We construct a morph from ${\mathrm{\Gamma }}_0$ to ${\mathrm{\Gamma }}_{1/2}$ in several stages as follows. First, we rotate ${\mathrm{\Gamma }}_0$ so that the resulting triangulation ${\mathrm{\Gamma }}_0^{\prime }$ is sinkable (as guaranteed by Conjecture 2.4) and then longitudinally morph ${\mathrm{\Gamma }}_0^{\prime }$ to a southern triangulation ${\mathrm{\Gamma }}_0^{\prime \prime }$.²²2If the triangulation ${\mathrm{\Gamma }}_0$ is not full, we can rotate it directly to a southern triangulation ${\mathrm{\Gamma }}_0^{\prime }={\mathrm{\Gamma }}_0^{\prime \prime }$. Similarly, we rotate ${\mathrm{\Gamma }}_{1/2}$ so that the resulting triangulation ${\mathrm{\Gamma }}_{1/2}^{\prime }$ has the same north face as ${\mathrm{\Gamma }}_0^{\prime }$ and ${\mathrm{\Gamma }}_0^{\prime \prime }$, and then longitudinally morph ${\mathrm{\Gamma }}_{1/2}^{\prime }$ to a southern triangulation ${\mathrm{\Gamma }}_{1/2}^{\prime \prime }$. Projection from the center of the sphere maps ${\mathrm{\Gamma }}_0^{\prime \prime }$ and ${\mathrm{\Gamma }}_{1/2}^{\prime \prime }$ to isomorphic straight-line triangulations in the plane $z=-1$, each with the same triangular outer face. We can construct a morph between these planar triangulations using any of several algorithms [11, 34, 7, 29, 2, 25, 40]; lifting this planar morph back to the sphere yields a spherical morph from ${\mathrm{\Gamma }}_0^{\prime \prime }$ to ${\mathrm{\Gamma }}_{1/2}^{\prime \prime }$. Our final morph is the concatenation of the rotation ${\mathrm{\Gamma }}_0\rightsquigarrow {\mathrm{\Gamma }}_0^{\prime }$, the longitudinal morph ${\mathrm{\Gamma }}_0^{\prime }\rightsquigarrow {\mathrm{\Gamma }}_0^{\prime \prime }$, the lifted planar morph ${\mathrm{\Gamma }}_0^{\prime \prime }\rightsquigarrow {\mathrm{\Gamma }}_{1/2}^{\prime \prime }$, the reverse of the longitudinal morph ${\mathrm{\Gamma }}_{1/2}^{\prime }\rightsquigarrow {\mathrm{\Gamma }}_{1/2}^{\prime \prime }$, and the reverse of the rotation ${\mathrm{\Gamma }}_{1/2}\rightsquigarrow {\mathrm{\Gamma }}_{1/2}^{\prime }$. See Figure 2.2 for an example (without the initial and final rotations).

We construct a morph ${\mathrm{\Gamma }}_1\rightsquigarrow {\mathrm{\Gamma }}_{1/2}$ using the same strategy. The final morph ${\mathrm{\Gamma }}_0\rightsquigarrow {\mathrm{\Gamma }}_1$ is the concatenation of ${\mathrm{\Gamma }}_0\rightsquigarrow {\mathrm{\Gamma }}_{1/2}$ and the reverse of ${\mathrm{\Gamma }}_1\rightsquigarrow {\mathrm{\Gamma }}_{1/2}$.

We characterize the shellability of $\mathrm{\Gamma }$ in terms of three directed graphs, which are illustrated in Figure 3.1.

• $\mathrm{■}$

  The directed dual graph ${𝚪}^{\mathbf{\downarrow }}$ contains a directed edge from face $f_i$ to face $f_j$ if and only if $f_i$ and $f_j$ share an edge in $\mathrm{\Gamma }$, and some point in $f_i$ is due north (on the same longitude) of some point in $f_j$.

• $\mathrm{■}$

  The oriented primal graph ${𝚪}^{\mathbf{\to }}$ is the directed dual of ${\mathrm{\Gamma }}^{\downarrow }$. For every undirected edge $ij$ of $\mathrm{\Gamma }$, the graph ${\mathrm{\Gamma }}^{\to }$ contains the directed edge $i\mathrm{\to }j$ if and only if vertex $j$ is east of vertex $i$, or more formally, if the determinant

  is positive, where $(x_i,y_i,z_i)$ is the coordinate vector for vertex $i$.

• $\mathrm{■}$

  Finally, ${𝚪}^{\mathbf{\searrow }\mathbf{\swarrow }}$ is a directed proper subgraph of $\mathrm{\Gamma }$ whose edges are the legs of each down-face, each directed toward its apex.

We defer the proof of the following lemma to the full version [24].

Each of the conditions (b), (c), (d), and (e) can be tested in $O(n)$ time using textbook graph algorithms. A straightforward extension of Lemma 3.1 to triangulations with vertical edges implies a theorem of Awartani and Henderson [4]: Every triangulation with longitudinal seam is longitudinally shellable. See the full version [24] for more details.

Instead of considering different rotations of $\mathrm{\Gamma }$, it is convenient to keep $\mathrm{\Gamma }$ fixed and consider different locations for the “north pole”. We call a unit vector $p$ a shelling direction for $\mathrm{\Gamma }$ if any (and therefore every) rotation of the sphere that takes $p$ to the standard north pole $(0,0,1)$ also takes $\mathrm{\Gamma }$ to a longitudinally shellable triangulation. We similarly define the directed graphs ${\mathrm{\Gamma }}^{\downarrow }(p)$ and ${\mathrm{\Gamma }}^{\to }(p)$ and ${\mathrm{\Gamma }}^{\mathbf{\searrow }\mathbf{\swarrow }}(p)$. For example, for any unit vector $p=(x,y,z)$, the graph ${\mathrm{\Gamma }}^{\to }(p)$ contains the edge $i\mathrm{\to }j$ if and only if

and $p$ is a shelling direction for $\mathrm{\Gamma }$ if and only if the graphs ${\mathrm{\Gamma }}^{\downarrow }(p)$ and ${\mathrm{\Gamma }}^{\mathbf{\searrow }\mathbf{\swarrow }}(p)$ are acyclic.

Regard each edge of the undirected dual graph ${\mathrm{\Gamma }}^{\ast }$ as a pair of opposing directed edges or darts. For any directed cycle ${\gamma }^{\ast }$ of darts in ${\mathrm{\Gamma }}^{\ast }$, the polar region $P\mathbf{(}{\gamma }^{\mathbf{\ast }}\mathbf{)}$ is the set of all north poles $p$ such that the directed dual graph ${\mathrm{\Gamma }}^{\downarrow }(p)$ contains every dart in ${\gamma }^{\ast }$. A unit vector $p$ is a shelling direction for $\mathrm{\Gamma }$ if and only if $p\notin P({\gamma }^{\ast })$ for every directed dual cycle ${\gamma }^{\ast }$.