Tightening curves and graphs on surfaces

curves;graphs;surfaces;tightening;homotopy;electrical transformations;Delta-Y transformations;plane graphs;smoothings;graph minors;medial;monotonic;untangling

Chang, Hsien-Chih

关键词: curves;    graphs;    surfaces;    tightening;    homotopy;    electrical transformations;    Delta-Y transformations;    plane graphs;    smoothings;    graph minors;    medial;    monotonic;    untangling;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/101519/CHANG-DISSERTATION-2018.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

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.