2026-07-25T01:47:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23199 2025-10-02T12:42:44Z ddc:004 open_access

Shelling and Sinking Graphs on the Sphere Erickson, Jeff Howard, Christian morphing planar graphs spherical graph drawing longitudinal shelling 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^{ω/2}) time, where ω 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jeff Erickson and Christian Howard 2025 Is Part Of LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2025.47 urn:nbn:de:0030-drops-231996 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.47 eng https://creativecommons.org/licenses/by/4.0/legalcode