Abstract
We consider two systems (α 1, …, α m ) and (β 1, …,β n ) of simple curves drawn on a compact two-dimensional surface M with boundary.
Each α i and each β j is either an arc meeting the boundary of M at its two endpoints, or a closed curve. The α i are pairwise disjoint except for possibly sharing endpoints, and similarly for the β j . We want to “untangle” the β j from the ai by a self-homeomorphism of M; more precisely, we seek a homeomorphism φ:M→M fixing the boundary of M pointwise such that the total number of crossings of the ai with the φ(β j ) is as small as possible. This problem is motivated by an application in the algorithmic theory of embeddings and 3-manifolds.
We prove that if M is planar, i.e., a sphere with h ≥ 0 boundary components (“holes”), then O(mn) crossings can be achieved (independently of h), which is asymptotically tight, as an easy lower bound shows.
In general, for an arbitrary (orientable or nonorientable) surface M with h holes and of (orientable or nonorientable) genus g ≥ 0, we obtain an O((m + n)4) upper bound, again independent of h and g.
The proofs rely, among other things, on a result concerning simultaneous planar drawings of graphs by Erten and Kobourov.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
T. Bläsius, S. G. Kobourov and I. Rutter, Simultaneous embedding of planar graphs, in Handbook of Graph Drawing and Visualization, Discrete Mathematics and its Applications, Vol. 81, Chapman and Hall/CRC Press, Boca Raton, FL, 2013, pp. 383–408; preprint available at http://arxiv.org/abs/1204.5853.
S. Cabello and B. Mohar, Finding shortest non-separating and non-contractible cycles for topologically embedded graphs, Discrete & Computational Geometry 37 2007, 213–235.
É. Colin de Verdière, Shortening of curves and decomposition of surfaces, PhD. Thesis, Univ. Paris 7, 2003.
É. Colin de Verdière, Topological algorithms for graphs on surfaces, Habilitation thesis, école Normale Supérieure, 2012; available at http://www.di.ens.fr/~colin/.
E. D. Demaine, F. V. Fomin, M. T. Hajiaghayi and D. M. Thilikos, Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs, Journal of the ACM 52 2005, 866–893.
C. Erten and S. G. Kobourov, Simultaneous embedding of planar graphs with few bends, Journal of Graph Algorithms and Applications 9 2005, 347–364 (electronic).
B. Farb and D. Margalit, A Primer on Mapping Class Groups, Princeton Mathematical Series, Vol. 49, Princeton University Press. Princeton, NJ, 2012.
G. K. Francis and J. R. Weeks, Conway’s ZIP proof, American Mathematical Monthly 106 1999, 393–399.
J. Geelen, T. Huynh and R. B. Richter, Explicit bounds for graph minors, 2013, preprint; arXiv:1305.1451.
T. Huynh, Removing intersections of curves in surfaces, Mathoverflow http://mathoverflow.net/questions/33963/ removing-intersections-of-curves-in-surfaces/33970#33970, 2010.
W. Jaco and E. Sedgwick, Decision problems in the space of Dehn fillings, Topology 42 2003, 845–906.
J. Kratochvíl and J. Matoušek, String graphs requiring huge representations, Journal of Combinatorial Theory. Series B 53 1991, 1–4.
M. Kaufmann and R. Wiese, Embedding vertices at points: few bends suffice for planar graphs, Graph Drawings and Represantions (Prague, 1999), Journal of Graph Algorithms and Applications 6 2002, 115–129 (electronic). Graph drawing and representations (Prague, 1999).
W. B. R. Lickorish, A representation of orientable combinatorial 3-manifolds, Annals of Mathematics 76 1962, 531–540.
F. Lazarus, M. Pocchiola, G. Vegter and A. Verroust, Computing a canonical polygonal schema of an orientable triangulated surface, in Proceedings of the 17th Annual Symposium on Computational Geometry (Medford, MA), ACM, New York, 2001, pp. 80–89.
J. Matoušek, E. Sedgwick, M. Tancer and U. Wagner, Embeddability in the 3-sphere is decidable, Extended abstract in the Proceedings of the 30th Annual ACM Symposium on Computational Geometry (SoCG), 2014, pp. 78–84. Preprint of the full version available at arXiv:1402.0815.
J. Matoušek, E. sedgwick, M. Tancer and U. Wagner, Hardness of embedding simplicial complexes in Rd, Journal of the European Mathematical Society 13 2011, 259–295.
B. Mohar and C. Thomassen, Graphs on Surfaces, Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2001.
M. Schaefer, E. Sedgwick and D. štefankovic, Recognizing string graphs in NP, Journal of Computer and System Sciences 67 2003, 365–380.
J. Stillwell, Classical Topology and Combinatorial Group Theory, Graduate Texts in Mathematics, Vol. 72, Springer-Verlag, New York–Berlin, 1980.
G. Vegter and C. K. Yap, Computational complexity of combinatorial surfaces, in Proceedings of the 6th Annual Symposium on Computational Geometry (Berkeley, CA), ACM, New York, NY, 1990, pp. 102–111.
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by the ERC Advanced Grant No. 267165.
Partially supported by Grant GRADR Eurogiga GIG/11/E023.
Supported by a Göran Gustafsson postdoctoral fellowship.
Supported by the Swiss National Science Foundation (Grant SNSF-PP00P2-138948).
Rights and permissions
About this article
Cite this article
Matoušek, J., Sedgwick, E., Tancer, M. et al. Untangling two systems of noncrossing curves. Isr. J. Math. 212, 37–79 (2016). https://doi.org/10.1007/s11856-016-1294-9
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11856-016-1294-9