Document Open Access Logo

Untangling Planar Curves

Authors Hsien-Chih Chang, Jeff Erickson

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2016.29.pdf
  • Filesize: 4.6 MB
  • 16 pages

Document Identifiers

Subject Classification

Keywords
  • computational topology
  • homotopy
  • planar graphs
  • Delta-Y transformations
  • defect
  • Reidemeister moves
  • tangles

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

Any generic closed curve in the plane can be transformed into a simple closed curve by a finite sequence of local transformations called homotopy moves.  We prove that simplifying a planar closed curve with n self-crossings requires Theta(n^{3/2}) homotopy moves in the worst case.  Our algorithm improves the best previous upper bound O(n^2), which is already implicit in the classical work of Steinitz; the matching lower bound follows from the construction of closed curves with large defect, a topological invariant of generic closed curves introduced by Aicardi and Arnold.  This lower bound also implies that Omega(n^{3/2}) degree-1 reductions, series-parallel reductions, and Delta-Y transformations are required to reduce any planar graph with treewidth Omega(sqrt{n}) to a single edge, matching known upper bounds for rectangular and cylindrical grid graphs.  Finally, we prove that Omega(n^2) homotopy moves are required in the worst case to transform one non-contractible closed curve on the torus to another; this lower bound is tight if the curve is homotopic to a simple closed curve.

Cite As Get BibTex

Hsien-Chih Chang and Jeff Erickson. Untangling Planar Curves. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.SoCG.2016.29

Author Details

Hsien-Chih Chang
Jeff Erickson

References

  1. Francesca Aicardi. Tree-like curves. In Vladimir I. Arnold, editor, Singularities and Bifurcations, volume 21 of Advances in Soviet Mathematics, pages 1-31. Amer. Math. Soc., 1994. Google Scholar
  2. Sheldon B. Akers, Jr. The use of wye-delta transformations in network simplification. Oper. Res., 8(3):311-323, 1960. Google Scholar
  3. James W. Alexander. Combinatorial analysis situs. Trans. Amer. Math. Soc., 28(2):301-326, 1926. Google Scholar
  4. James W. Alexander and G. B. Briggs. On types of knotted curves. Ann. Math., 28(1/4):562-586, 1926-1927. Google Scholar
  5. Sigurd Angenent. Prabolic equations for curves on surfaces: Part II. Intersections, blow-up and generalized solutions. Ann. Math., 133(1):171-215, 1991. Google Scholar
  6. Dan Archdeacon, Charles J. Colbourn, Isidoro Gitler, and J. Scott Provan. Four-terminal reducibility and projective-planar wye-delta-wye-reducible graphs. J. Graph Theory, 33(2):83-93, 2000. Google Scholar
  7. Vladimir I. Arnold. Plane curves, their invariants, perestroikas and classifications. In Vladimir I. Arnold, editor, Singularities and Bifurcations, volume 21 of Adv. Soviet Math., pages 33-91. Amer. Math. Soc., 1994. Google Scholar
  8. Vladimir I. Arnold. Topological Invariants of Plane Curves and Caustics, volume 5 of University Lecture Series. Amer. Math. Soc., 1994. Google Scholar
  9. Hsien-Chih Chang and Jeff Erickson. Electrical reduction, homtoopy moves, and defect. Preprint, October 2015. URL: http://arxiv.org/abs/1510.00571.
  10. Sergei Chmutov, Sergei Duzhin, and Jacob Mostovoy. Introduction to Vassiliev knot invariants. Cambridge Univ. Press, 2012. Google Scholar
  11. Charles J. Colbourn, J. Scott Provan, and Dirk Vertigan. A new approach to solving three combinatorial enumeration problems on planar graphs. Discrete Appl. Math., 60:119-129, 1995. Google Scholar
  12. Yves Colin de Verdière, Isidoro Gitler, and Dirk Vertigan. Réseaux électriques planaires II. Comment. Math. Helvetici, 71(144-167), 1996. Google Scholar
  13. John H. Conway. An enumeration of knots and links, and some of their algebraic properties. In by:John Leech, editor, Computational Problems in Abstract Algebra, pages 329-358. Pergamon Press, 1970. Google Scholar
  14. Maurits de Graaf and Alexander Schrijver. Making curves minimally crossing by Reidemeister moves. J. Comb. Theory Ser. B, 70(1):134–156, 1997. Google Scholar
  15. G. V. Epifanov. Reduction of a plane graph to an edge by a star-triangle transformation. Dokl. Akad. Nauk SSSR, 166:19-22, 1966. In Russian. English translation in Soviet Math. Dokl. 7:13-17, 1966. Google Scholar
  16. Chaim Even-Zohar, Joel Hass, Nati Linial, and Tahl Nowik. Invariants of random knots and links. Preprint, November 2014. URL: http://arxiv.org/abs/1411.3308.
  17. Thomas A. Feo and J. Scott Provan. Delta-wye transformations and the efficient reduction of two-terminal planar graphs. Oper. Res., 41(3):572-582, 1993. Google Scholar
  18. Thomas Aurelio Feo. I. A Lagrangian Relaxation Method for Testing The Infeasibility of Certain VLSI Routing Problems. II. Efficient Reduction of Planar Networks For Solving Certain Combinatorial Problems. PhD thesis, Univ. California Berkeley, 1985. Google Scholar
  19. George K. Francis. The folded ribbon theorem: A contribution to the study of immersed circles. Trans. Amer. Math. Soc., 141:271-303, 1969. Google Scholar
  20. Carl Friedrich Gauß. Nachlass. I. Zur Geometria situs. In Werke, volume 8, pages 271-281. Teubner, 1900. Originally written between 1823 and 1840. Google Scholar
  21. Isidoro Gitler. Delta-wye-delta Transformations: Algorithms and Applications. PhD thesis, Department of Combinatorics and Optimization, University of Waterloo, 1991. Google Scholar
  22. Matthew A. Grayson. Shortening embedded curves. Ann. Math., 129(1):71-111, 1989. Google Scholar
  23. Branko Grünbaum. Convex Polytopes. Number XVI in Monographs in Pure and Applied Mathematics. John Wiley &Sons, 1967. Google Scholar
  24. Joel Hass and Peter Scott. Intersections of curves on surfaces. Israel J. Math., 51:90-120, 1985. Google Scholar
  25. Joel Hass and Peter Scott. Shortening curves on surfaces. Topology, 33(1):25-43, 1994. Google Scholar
  26. Chuichiro Hayashi and Miwa Hayashi. Minimal sequences of Reidemeister moves on diagrams of torus knots. Proc. Amer. Math. Soc., 139:2605-2614, 2011. Google Scholar
  27. Chuichiro Hayashi, Miwa Hayashi, Minori Sawada, and Sayaka Yamada. Minimal unknotting sequences of Reidemeister moves containing unmatched RII moves. J. Knot Theory Ramif., 21(10):1250099 (13 pages), 2012. Google Scholar
  28. Noburo Ito and Yusuke Takimura. (1,2) and weak (1,3) homotopies on knot projections. J. Knot Theory Ramif., 22(14):1350085 (14 pages), 2013. Addendum in J. Knot Theory Ramif. 23(8):1491001 (2 pages), 2014. Google Scholar
  29. Arthur Edwin Kennelly. Equivalence of triangles and three-pointed stars in conducting networks. Electrical World and Engineer, 34(12):413-414, 1899. Google Scholar
  30. Mikhail Khovanov. Doodle groups. Trans. Amer. Math. Soc., 349(6):2297-2315, 1997. Google Scholar
  31. Hiroyuki Nakahara and Hiromitsu Takahashi. An algorithm for the solution of a linear system by Δ-Y transformations. IEICE Trans. Fundamentals of Electronics, Communications and Computer Sciences, E79-A(7):1079-1088, 1996. Google Scholar
  32. Steven D. Noble and Dominic J. A. Welsh. Knot graphs. J. Graph Theory, 34(1):100-111, 2000. Google Scholar
  33. Tahl Nowik. Complexity of planar and spherical curves. Duke J. Math., 148(1):107-118, 2009. Google Scholar
  34. Jane M. Paterson. A combinatorial algorithm for immersed loops in surfaces. Topology Appl., 123:205-234, 2002. Google Scholar
  35. Michael Polyak. Invariants of curves and fronts via Gauss diagrams. Topology, 37(5):989-1009, 1998. Google Scholar
  36. Kurt Reidemeister. Elementare Begründung der Knotentheorie. Abh. Math. Sem. Hamburg, 5:24-32, 1927. Google Scholar
  37. Neil Robertson and Paul D. Seymour. Graph minors. X. Obstructions to tree-decomposition. J. Comb. Theory Ser. B, 52(2):153-190, 1991. Google Scholar
  38. Neil Robertson, Paul D. Seymour, and Robin Thomas. Quickly excluding a planar graph. J. Comb. Theory Ser. B, 62(2):232-348, 1994. Google Scholar
  39. Alexander Russell. The method of duality. In A Treatise on the Theory of Alternating Currents, chapter XVII, pages 380-399. Cambridge Univ. Press, 1904. Google Scholar
  40. Xiaohuan Song. Implementation issues for Feo and Provan’s delta-wye-delta reduction algorithm. M.Sc. Thesis, University of Victoria, 2001. Google Scholar
  41. Ernst Steinitz. Polyeder und Raumeinteilungen. Enzyklopädie der mathematischen Wissenschaften mit Einschluss ihrer Anwendungen, III.AB(12):1-139, 1916. Google Scholar
  42. Ernst Steinitz and Hans Rademacher. Vorlesungen über die Theorie der Polyeder: unter Einschluß der Elemente der Topologie, volume 41 of Grundlehren der mathematischen Wissenschaften. Springer-Verlag, 1934. Reprinted 1976. Google Scholar
  43. Klaus Truemper. On the delta-wye reduction for planar graphs. J. Graph Theory, 13(2):141-148, 1989. Google Scholar
  44. Leslie S. Valiant. Universality considerations in VLSI circuits. IEEE Trans. Comput., C-30(2):135-140, 1981. Google Scholar
  45. Gert Vegter. Kink-free deformation of polygons. In Proceedings of the 5th Annual Symposium on Computational Geometry, pages 61-68, 1989. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact