{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/101519"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/101519","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Tightening curves and graphs on surfaces","abstract":"Any continuous deformation of closed curves on a surface can be decomposed into a finite sequence of local changes on the structure of the curves; we refer to such local operations as homotopy moves. Tightening is the process of deforming given curves into their minimum position; that is, those with minimum number of self-intersections. While such operations and the tightening process has been studied extensively, surprisingly little is known about the quantitative bounds on the number of homotopy moves required to tighten an arbitrary curve. An unexpected connection exists between homotopy moves and a set of local operations on graphs called electrical transformations. Electrical transformations have been used to simplify electrical networks since the 19th century; later they have been used for solving various combinatorial problems on graphs, as well as applications in statistical mechanics, robotics, and quantum mechanics. Steinitz, in his study of 3-dimensional polytopes, looked at the electrical transformations through the lens of medial construction, and implicitly established the connection to homotopy moves; later the same observation has been discovered independently in the context of knots. In this thesis, we study the process of tightening curves on surfaces using homotopy moves and their consequences on electrical transformations from a quantitative perspective. To derive upper and lower bounds we utilize tools like curve invariants, surface theory, combinatorial topology, and hyperbolic geometry. We develop several new tools to construct efficient algorithms on tightening curves and graphs, as well as to present examples where no efficient algorithm exists. We then argue that in order to study electrical transformations, intuitively it is most beneficial to work with monotonic homotopy moves instead, where no new crossings are created throughout the process; ideas and proof techniques that work for monotonic homotopy moves should transfer to those for electrical transformations. We present conjectures and partial evidence supporting the argument.","abstract_html":"Any continuous deformation of closed curves on a surface can be decomposed into a finite sequence of local changes on the structure of the curves; we refer to such local operations as homotopy moves. Tightening is the process of deforming given curves into their minimum position; that is, those with minimum number of self-intersections. While such operations and the tightening process has been studied extensively, surprisingly little is known about the quantitative bounds on the number of homotopy moves required to tighten an arbitrary curve. An unexpected connection exists between homotopy moves and a set of local operations on graphs called electrical transformations. Electrical transformations have been used to simplify electrical networks since the 19th century; later they have been used for solving various combinatorial problems on graphs, as well as applications in statistical mechanics, robotics, and quantum mechanics. Steinitz, in his study of 3-dimensional polytopes, looked at the electrical transformations through the lens of medial construction, and implicitly established the connection to homotopy moves; later the same observation has been discovered independently in the context of knots. In this thesis, we study the process of tightening curves on surfaces using homotopy moves and their consequences on electrical transformations from a quantitative perspective. To derive upper and lower bounds we utilize tools like curve invariants, surface theory, combinatorial topology, and hyperbolic geometry. We develop several new tools to construct efficient algorithms on tightening curves and graphs, as well as to present examples where no efficient algorithm exists. We then argue that in order to study electrical transformations, intuitively it is most beneficial to work with monotonic homotopy moves instead, where no new crossings are created throughout the process; ideas and proof techniques that work for monotonic homotopy moves should transfer to those for electrical transformations. We present conjectures and partial evidence supporting the argument.","abstract_has_math":false,"creators":["Chang, Hsien-Chih"],"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","Chekuri, Chandra","Dunfield, Nathan M.","Eppstein, David","Kolla, Alexandra"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2018,"date_issued":"2018-09-27T16:17:35Z","date_published":"2018-09-27T16:17:35Z","updated_at":"2026-07-22T22:24:40Z","subjects":["curves","graphs","surfaces","tightening","homotopy","electrical transformations","Delta-Y transformations","plane graphs","smoothings","graph minors","medial","monotonic","untangling"],"languages":["en"],"rights":["Copyright 2018 by Hsien-Chih Chang"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/101519","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Erickson, Jeff","Chekuri, Chandra","Dunfield, Nathan M.","Eppstein, David","Kolla, Alexandra"]},{"key":"dc:creator","label":"Author","values":["Chang, Hsien-Chih"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2018-09-27T16:17:35Z","2018-07-03","2018-08"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"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":["curves","graphs","surfaces","tightening","homotopy","electrical transformations","Delta-Y transformations","plane graphs","smoothings","graph minors","medial","monotonic","untangling"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2018 by Hsien-Chih Chang"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/101519"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Any continuous deformation of closed curves on a surface can be decomposed into a finite sequence of local changes on the structure of the curves; we refer to such local operations as homotopy moves. Tightening is the process of deforming given curves into their minimum position; that is, those with minimum number of self-intersections. While such operations and the tightening process has been studied extensively, surprisingly little is known about the quantitative bounds on the number of homotopy moves required to tighten an arbitrary curve. An unexpected connection exists between homotopy moves and a set of local operations on graphs called electrical transformations. Electrical transformations have been used to simplify electrical networks since the 19th century; later they have been used for solving various combinatorial problems on graphs, as well as applications in statistical mechanics, robotics, and quantum mechanics. Steinitz, in his study of 3-dimensional polytopes, looked at the electrical transformations through the lens of medial construction, and implicitly established the connection to homotopy moves; later the same observation has been discovered independently in the context of knots. In this thesis, we study the process of tightening curves on surfaces using homotopy moves and their consequences on electrical transformations from a quantitative perspective. To derive upper and lower bounds we utilize tools like curve invariants, surface theory, combinatorial topology, and hyperbolic geometry. We develop several new tools to construct efficient algorithms on tightening curves and graphs, as well as to present examples where no efficient algorithm exists. We then argue that in order to study electrical transformations, intuitively it is most beneficial to work with monotonic homotopy moves instead, where no new crossings are created throughout the process; ideas and proof techniques that work for monotonic homotopy moves should transfer to those for electrical transformations. We present conjectures and partial evidence supporting the argument.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2018-09-27 without embargo terms","The student, Hsien-Chih Chang, accepted the attached license on 2018-07-02 at 14:40.","The student, Hsien-Chih Chang, submitted this Dissertation for approval on 2018-07-02 at 14:52.","This Dissertation was approved for publication on 2018-07-03 at 12:00.","DSpace SAF Submission Ingestion Package generated from Vireo submission #12704 on 2018-09-27 at 10:46:20","Made available in DSpace on 2018-09-27T16:17:35Z (GMT). No. of bitstreams: 3 CHANG-DISSERTATION-2018.pdf: 4160186 bytes, checksum: f4def116772025b92bdbdda8bc9d488c (MD5) LICENSE.txt: 4213 bytes, checksum: 3ab5b7ed7d6b2f0c822e00495272e285 (MD5) PROQUEST_LICENSE.txt: 4559 bytes, checksum: 18cc523c7c3f7ace502e42e328c1d039 (MD5) Previous issue date: 2018-07-03"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Tightening curves and graphs on surfaces"]}]}],"canonical_facts":{"dc:contributor":["Erickson, Jeff","Chekuri, Chandra","Dunfield, Nathan M.","Eppstein, David","Kolla, Alexandra"],"dc:creator":["Chang, Hsien-Chih"],"dc:date":["2018-09-27T16:17:35Z","2018-07-03","2018-08"],"dc:description":["Any continuous deformation of closed curves on a surface can be decomposed into a finite sequence of local changes on the structure of the curves; we refer to such local operations as homotopy moves. Tightening is the process of deforming given curves into their minimum position; that is, those with minimum number of self-intersections. While such operations and the tightening process has been studied extensively, surprisingly little is known about the quantitative bounds on the number of homotopy moves required to tighten an arbitrary curve. An unexpected connection exists between homotopy moves and a set of local operations on graphs called electrical transformations. Electrical transformations have been used to simplify electrical networks since the 19th century; later they have been used for solving various combinatorial problems on graphs, as well as applications in statistical mechanics, robotics, and quantum mechanics. Steinitz, in his study of 3-dimensional polytopes, looked at the electrical transformations through the lens of medial construction, and implicitly established the connection to homotopy moves; later the same observation has been discovered independently in the context of knots. In this thesis, we study the process of tightening curves on surfaces using homotopy moves and their consequences on electrical transformations from a quantitative perspective. To derive upper and lower bounds we utilize tools like curve invariants, surface theory, combinatorial topology, and hyperbolic geometry. We develop several new tools to construct efficient algorithms on tightening curves and graphs, as well as to present examples where no efficient algorithm exists. We then argue that in order to study electrical transformations, intuitively it is most beneficial to work with monotonic homotopy moves instead, where no new crossings are created throughout the process; ideas and proof techniques that work for monotonic homotopy moves should transfer to those for electrical transformations. We present conjectures and partial evidence supporting the argument.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2018-09-27 without embargo terms","The student, Hsien-Chih Chang, accepted the attached license on 2018-07-02 at 14:40.","The student, Hsien-Chih Chang, submitted this Dissertation for approval on 2018-07-02 at 14:52.","This Dissertation was approved for publication on 2018-07-03 at 12:00.","DSpace SAF Submission Ingestion Package generated from Vireo submission #12704 on 2018-09-27 at 10:46:20","Made available in DSpace on 2018-09-27T16:17:35Z (GMT). No. of bitstreams: 3 CHANG-DISSERTATION-2018.pdf: 4160186 bytes, checksum: f4def116772025b92bdbdda8bc9d488c (MD5) LICENSE.txt: 4213 bytes, checksum: 3ab5b7ed7d6b2f0c822e00495272e285 (MD5) PROQUEST_LICENSE.txt: 4559 bytes, checksum: 18cc523c7c3f7ace502e42e328c1d039 (MD5) Previous issue date: 2018-07-03"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/101519"],"dc:language":["en"],"dc:rights":["Copyright 2018 by Hsien-Chih Chang"],"dc:subject":["curves","graphs","surfaces","tightening","homotopy","electrical transformations","Delta-Y transformations","plane graphs","smoothings","graph minors","medial","monotonic","untangling"],"dc:title":["Tightening curves and graphs on surfaces"],"dc:type":["text"],"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:40Z"}