Equilibrium graphs on the flat torus or finding zen amidst the bull

Tutte's classical spring embedding theorem, and equilibrium graphs on the plane in general, have been a subject of study for many decades, with connections to and applications in many areas, including, but not limited to, discrete geometry, planar graph theory, graphics, surface parametrization, mechanical engineering, and graphical statics. In his 1963 paper, Tutte observed, “[W]e may remark that very little is known about representations of graphs in the protective plane and higher surfaces.” Six decades since Tutte's observation, however, our understanding of the properties and applications of equilibrium graphs on higher genus surfaces is still surprisingly limited, despite a growing body of work suggesting the utility of furthering this understanding. In this thesis, we extend some existing structural properties and algorithmic applications of equilibrium graphs on the plane to the setting of flat tori. In particular, we consider the classical Maxwell–Cremona correspondence and a number of different planar morphing algorithms. The Maxwell–Cremona correspondence, through a more modern computational geometry lens, can be summarized as stating that a planar graph is in positive equilibrium if and only if it is a weighted Delaunay graph of its point set. We derive some partial generalizations of this correspondence in the toroidal setting. In particular, we show that, whereas weighted Delaunay still implies positive equilibrium on flat tori, the converse is not always true; however, we give a full characterization of when the converse holds. Next, we present generalizations of a few different techniques for morphing planar graphs. We show that techniques by Cairns and by Floater and Gotsman generalize to the toroidal setting with minor modifications; our generalization of the latter also provides a short proof of a conjecture of Connelly et al. for geodesic torus triangulations. On the other hand, Alamdari et al.'s improvement of Cairns' method uses techniques that do not seem to generalize. Instead, we obtain a similar improvement via a novel technique using toroidal spring embeddings, and then adapt said new technique to derive a new, simpler planar morphing algorithm.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2022

Author dc:creator

• Lin, Patrick

Contributors dc:contributor

• Erickson, Jeff
• Chan, Timothy
• Chekuri, Chandra
• Lubiw, Anna

• morphing
• spring embedding
• toroidal graphs
• combinatorial topology
• geometric graphs
• homology
• flat torus

Statement dc:rights

• © 2021 Patrick Lin

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/113003

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/113003