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

Lin, Patrick

Permalink

https://hdl.handle.net/2142/113003 Copy

Description

Title

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

Author(s)

Lin, Patrick

Issue Date

2021-07-12

Director of Research (if dissertation) or Advisor (if thesis)

Erickson, Jeff

Doctoral Committee Chair(s)

Erickson, Jeff

Committee Member(s)

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

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

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

Abstract

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.

Graduation Semester

2021-08

Type of Resource

Thesis

Permalink

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

Copyright and License Information

© 2021 Patrick Lin

Owning Collections