Untangling planar curves
type: Item
instance of: scholarly article
title: Untangling planar curves
zbMATH Open document ID: 1387.57039
author: Hsien-Chih Chang
author: Jeff Erickson
published in: Discrete \& Computational Geometry
publication date: 2018-01-11T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/5921/
review text: A homotopy move is a local transformation taking a closed planar curve to a simple closed curve. The authors prove that to simplify a planar closed curve having \(n\) self crossings needs at most \(O(n^{3/2})\) homotopy moves. Hence they improve the previous bound of \(O(n^2)\). They also improve some other bounds similarly like the bound for a transformation taking one immersion of \(k\) circles having at most \(n\) self crossings into another. Also they prove that transforming a non-contractible closed curve to another one on an orientable surface needs a maximum of \(\Omega(n^2)\) homotopy moves. This is a nice paper combining surface topology, graph theory and combinatorics.
Mathematics Subject Classification ID: 57N35
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 68U05
zbMATH DE Number: 6824885
zbMATH Keywords: curves on surfaces
zbMATH Keywords: homotopy
zbMATH Keywords: curve invariants
zbMATH Keywords: planar graphs
zbMATH Keywords: \(\Delta \mathrm{Y}\) transformations
reviewed by: Ismail Naci Cangül
MaRDI profile type: Publication
OpenAlex ID: W2741773415
cites work: Q4325485
cites work: The Use of Wye-Delta Transformations in Network Simplification
cites work: Incremental Voronoi diagrams
cites work: Parabolic equations for curves on surfaces. II: Intersections, blow-up and generalized solutions
cites work: Four-terminal reducibility and projective-planar wye-delta-wye-reducible graphs
cites work: Q4325486
cites work: Q4305594
cites work: Q5452284
cites work: Untangling Planar Curves
cites work: An optimal algorithm for intersecting line segments in the plane
cites work: Introduction to Vassiliev knot invariants
cites work: Applications of random sampling in computational geometry. II
cites work: A new approach to solving three combinatorial enumeration problems on planar graphs
cites work: Planar electric networks. II
cites work: Q5601331
cites work: An upper bound on Reidemeister moves
cites work: Q3579467
cites work: Q5528477
cites work: Invariants of random knots and links
cites work: Delta-Wye Transformations and the Efficient Reduction of Two-Terminal Planar Graphs
cites work: The Folded Ribbon Theorem. A Contribution to the Study of Immersed Circles
cites work: Wye-Delta Transformation in Probablilistic Networks
cites work: Doodle groups
cites work: Making curves minimally crossing by Reidemeister moves
cites work: Shortening embedded curves
cites work: Q5547252
cites work: Primitives for the manipulation of general subdivisions and the computation of Voronoi
cites work: Unknot diagrams requiring a quadratic number of Reidemeister moves to untangle
cites work: Intersections of curves on surfaces
cites work: Shortening curves on surfaces
cites work: Minimal sequences of Reidemeister moves on diagrams of torus knots
cites work: Unknotting number and number of Reidemeister moves needed for unlinking
cites work: Minimal unknotting sequences of Reidemeister moves containing unmatched RII moves
cites work: (1, 2) AND WEAK (1, 3) HOMOTOPIES ON KNOT PROJECTIONS
cites work: A polynomial upper bound on Reidemeister moves
cites work: A fast planar partition algorithm. I
cites work: Q4487078
cites work: Complexity of plane and spherical curves
cites work: A combinatorial algorithm for immersed loops in surfaces
cites work: Invariants of curves and fronts via Gauss diagrams
cites work: Graph minors. X: Obstructions to tree-decomposition
cites work: Quickly excluding a planar graph
cites work: Q4089424
cites work: On minimal-node-cost planar embeddings
cites work: On the delta-wye reduction for planar graphs
cites work: Q4004142
cites work: Universality considerations in VLSI circuits
DOI: 10.1007/S00454-017-9907-6
description: scientific article; zbMATH DE number 6824885