{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/113003"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/113003","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Equilibrium graphs on the flat torus or finding zen amidst the bull","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Lin, Patrick"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Erickson, Jeff","Chan, Timothy","Chekuri, Chandra","Lubiw, Anna"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-01-12T21:45:30Z","date_published":"2022-01-12T21:45:30Z","updated_at":"2026-07-22T22:24:52Z","subjects":["morphing","spring embedding","toroidal graphs","combinatorial topology","geometric graphs","homology","flat torus"],"languages":["en"],"rights":["© 2021 Patrick Lin"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/113003","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Erickson, Jeff","Chan, Timothy","Chekuri, Chandra","Lubiw, Anna"]},{"key":"dc:creator","label":"Author","values":["Lin, Patrick"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2022-01-12T21:45:30Z","2021-07-12","2021-08"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["morphing","spring embedding","toroidal graphs","combinatorial topology","geometric graphs","homology","flat torus"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["© 2021 Patrick Lin"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/113003"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-01-12 without embargo terms","The student, Patrick Lin, accepted the attached license on 2021-07-08 at 21:44.","The student, Patrick Lin, submitted this Dissertation for approval on 2021-07-08 at 21:48.","This Dissertation was approved for publication on 2021-07-12 at 11:01.","DSpace SAF Submission Ingestion Package generated from Vireo submission #16813 on 2022-01-12 at 12:44:30","Made available in DSpace on 2022-01-12T21:45:30Z (GMT). No. of bitstreams: 3 LIN-DISSERTATION-2021.pdf: 5143539 bytes, checksum: c964c6cc8fcb206679abf8656ddde4c6 (MD5) LICENSE.txt: 4208 bytes, checksum: e7f66dd51b8f4c6f121a8c73220826dd (MD5) PROQUEST_LICENSE.txt: 4554 bytes, checksum: 2b0eb5efb4369ddc6cfe344a240dc08c (MD5) Previous issue date: 2021-07-12"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Equilibrium graphs on the flat torus or finding zen amidst the bull"]}]}],"canonical_facts":{"dc:contributor":["Erickson, Jeff","Chan, Timothy","Chekuri, Chandra","Lubiw, Anna"],"dc:creator":["Lin, Patrick"],"dc:date":["2022-01-12T21:45:30Z","2021-07-12","2021-08"],"dc:description":["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.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-01-12 without embargo terms","The student, Patrick Lin, accepted the attached license on 2021-07-08 at 21:44.","The student, Patrick Lin, submitted this Dissertation for approval on 2021-07-08 at 21:48.","This Dissertation was approved for publication on 2021-07-12 at 11:01.","DSpace SAF Submission Ingestion Package generated from Vireo submission #16813 on 2022-01-12 at 12:44:30","Made available in DSpace on 2022-01-12T21:45:30Z (GMT). No. of bitstreams: 3 LIN-DISSERTATION-2021.pdf: 5143539 bytes, checksum: c964c6cc8fcb206679abf8656ddde4c6 (MD5) LICENSE.txt: 4208 bytes, checksum: e7f66dd51b8f4c6f121a8c73220826dd (MD5) PROQUEST_LICENSE.txt: 4554 bytes, checksum: 2b0eb5efb4369ddc6cfe344a240dc08c (MD5) Previous issue date: 2021-07-12"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/113003"],"dc:language":["en"],"dc:rights":["© 2021 Patrick Lin"],"dc:subject":["morphing","spring embedding","toroidal graphs","combinatorial topology","geometric graphs","homology","flat torus"],"dc:title":["Equilibrium graphs on the flat torus or finding zen amidst the bull"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:52Z"}