Untangling planar curves
From MaRDI portal
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.
Recommendations
Cites work
- (1, 2) AND WEAK (1, 3) HOMOTOPIES ON KNOT PROJECTIONS
- A combinatorial algorithm for immersed loops in surfaces
- A fast planar partition algorithm. I
- A new approach to solving three combinatorial enumeration problems on planar graphs
- A polynomial upper bound on Reidemeister moves
- An optimal algorithm for intersecting line segments in the plane
- An upper bound on Reidemeister moves
- Applications of random sampling in computational geometry. II
- Complexity of plane and spherical curves
- Computational geometry. Algorithms and applications.
- Delta-Wye Transformations and the Efficient Reduction of Two-Terminal Planar Graphs
- Doodle groups
- Four-terminal reducibility and projective-planar wye-delta-wye-reducible graphs
- Graph minors. X: Obstructions to tree-decomposition
- scientific article; zbMATH DE number 5764874 (Why is no real title available?)
- scientific article; zbMATH DE number 53949 (Why is no real title available?)
- scientific article; zbMATH DE number 3509333 (Why is no real title available?)
- scientific article; zbMATH DE number 638756 (Why is no real title available?)
- scientific article; zbMATH DE number 732196 (Why is no real title available?)
- scientific article; zbMATH DE number 732197 (Why is no real title available?)
- scientific article; zbMATH DE number 1462935 (Why is no real title available?)
- scientific article; zbMATH DE number 3241109 (Why is no real title available?)
- scientific article; zbMATH DE number 3261280 (Why is no real title available?)
- scientific article; zbMATH DE number 3321941 (Why is no real title available?)
- Incremental Voronoi diagrams
- Intersections of curves on surfaces
- Introduction to Vassiliev knot invariants
- Invariants of curves and fronts via Gauss diagrams
- Invariants of random knots and links
- Making curves minimally crossing by Reidemeister moves
- Minimal sequences of Reidemeister moves on diagrams of torus knots
- Minimal unknotting sequences of Reidemeister moves containing unmatched RII moves
- On minimal-node-cost planar embeddings
- On the delta-wye reduction for planar graphs
- Parabolic equations for curves on surfaces. II: Intersections, blow-up and generalized solutions
- Planar electric networks. II
- Primitives for the manipulation of general subdivisions and the computation of Voronoi
- Quickly excluding a planar graph
- Shortening curves on surfaces
- Shortening embedded curves
- The Folded Ribbon Theorem. A Contribution to the Study of Immersed Circles
- The Use of Wye-Delta Transformations in Network Simplification
- Universality considerations in VLSI circuits
- Unknot diagrams requiring a quadratic number of Reidemeister moves to untangle
- Unknotting number and number of Reidemeister moves needed for unlinking
- Untangling planar curves
- Wye-Delta Transformation in Probablilistic Networks
Cited in
(28)- Complexity of plane and spherical curves
- Making curves minimally crossing by Reidemeister moves
- Coaxing a planar curve to comply
- A combinatorial algorithm for immersed loops in surfaces
- Untangling a polygon
- Characterizing homotopy of systems of curves on a compact surface by crossing numbers
- An algorithm for delta-wye reduction of almost-planar graphs
- Structure and enumeration of \(K_4\)-minor-free links and link-diagrams
- Measuring complexity of curves on surfaces
- The unbearable hardness of unknotting
- Combinatorial properties of self-overlapping curves and interior boundaries
- Untangling planar curves
- scientific article; zbMATH DE number 4079447 (Why is no real title available?)
- Complexity of geodesics on 2-dimensional ideal polyhedra and isotopies
- Winding indexes of max. and min. Hamiltonians in N-gons
- scientific article; zbMATH DE number 7015040 (Why is no real title available?)
- Converting homotopies to isotopies and dividing homotopies in half in an effective way
- Lower bounds for electrical reduction on surfaces
- The unbearable hardness of unknotting
- Closing curves by rearranging arcs
- A Markov Chain Sampler for Plane Curves
- On the necessity of Reidemeister move 2 for simplifying immersed planar curves
- Tightening Curves on Surfaces Monotonically with Applications
- From curves to words and back again: geometric computation of minimum-area homotopy
- A Lagrangian filling for every cluster seed
- Properly immersed curves in arbitrary surfaces via apparent contours on spines of traversing flows
- Bringing closed polygonal curves in the plane to normal form via local moves
- Determining the orientation of closed planar curves
This page was built for publication: Untangling planar curves
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1688858)
