Untangling Two Systems of Noncrossing Curves

Matoušek, Jiří and Sedgwick, Eric and Tancer, Martin and Wagner, Uli (2013) Untangling Two Systems of Noncrossing Curves. In: 21st International Symposium, GD 2013, September 23-25, 2013, Bordeaux, France , pp. 472-483 (Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_41).

Full text not available from this repository.


We consider two systems (α 1,…,α m ) and (β 1,…,β n ) of curves drawn on a compact two-dimensional surface  with boundary. Each α i and each β j is either an arc meeting the boundary of  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 α i by a self-homeomorphism of  ; more precisely, we seek an homeomorphism φ→ fixing the boundary of  pointwise such that the total number of crossings of the α i 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  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  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.

Item Type:Conference Paper
Classifications:Z Theory > Z.250 Geometry
Z Theory > Z.750 Topology
ID Code:1398

Repository Staff Only: item control page


Bläsius, T., Kobourov, S.G., Rutter, I.: Simultaneous embedding of planar graphs (2012) (preprint), http://arxiv.org/abs/1204.5853

Erten, C., Kobourov, S.G.: Simultaneous embedding of planar graphs with few bends. J. Graph Algorithms Appl. 9(3), 347–364 (2005) (electronic)

Farb, B., Margalit, D.: A primer on mapping class groups. Princeton University Press, Princeton (2011)

Geelen, J., Huynh, T., Richter, R.B.: Explicit bounds for graph minors (May 2013) (preprint), http://arxiv.org/abs/1305.1451

Huynh, T.: Removing intersections of curves in surfaces. Mathoverflow (2010), http://mathoverflow.net/questions/33963/removing-intersections-of-curves-in-surfaces/33970#33970

Jaco, W., Sedgwick, E.: Decision problems in the space of Dehn fillings. Topology 42(4), 845–906 (2003)

Kratochvíl, J., Matoušek, J.: String graphs requiring huge representations. J. Combin. Theory Ser. B 53(1), 1–4 (1991)

Kaufmann, M., Wiese, R.: Embedding vertices at points: few bends suffice for planar graphs. J. Graph Algorithms Appl. 6(1), 115–129 (2002); (electronic) Graph drawing and representations, Prague (1999)

Lickorish, W.B.R.: A representation of orientable combinatorial 3-manifolds. Ann. Math (2) 76, 531–540 (1962)

Mohar, B., Thomassen, C.: Graphs on Surfaces. Johns Hopkins University Press, Baltimore (2001)

Matoušek, J., Tancer, M., Wagner, U.: Hardness of embedding simplicial complexes in ℝd. J. Eur. Math. Soc. 13(2), 259–295 (2011)

Schaefer, M., Sedgwick, E., Štefankovič, D.: Recognizing string graphs in NP. J. Comput. Syst. Sci. 67(2), 365–380 (2003)

Stillwell, J.: Classical Topology and Combinatorial Group Theory. Springer, New York (1980)