Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
UNTANGLING TWO SYSTEMS OF NONCROSSING CURVES
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.). Charles University, Czech Republic.
2016 (English)In: Israel Journal of Mathematics, ISSN 0021-2172, E-ISSN 1565-8511, Vol. 212, no 1, p. 37-79Article in journal (Refereed) Published
Resource type
Text
Abstract [en]

We consider two systems (alpha(1), ... ,alpha(m)) and (beta(1), ... , beta(n)) of simple curves drawn on a compact two-dimensional surface M with boundary. Each alpha(i) and each beta(j) is either an arc meeting the boundary of M at its two endpoints, or a closed curve. The a, are pairwise disjoint except for possibly sharing endpoints, and similarly for the beta(j). We want to "untangle" the beta(j) from the alpha(i) by a self-homeomorphism of M; more precisely, we seek a homeomorphism phi: M -> M fixing the boundary of M pointwise such that the total number of crossings of the a, with the phi(beta(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.

Place, publisher, year, edition, pages
Springer-Verlag New York, 2016. Vol. 212, no 1, p. 37-79
National Category
Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-189397DOI: 10.1007/s11856-016-1294-9ISI: 000377265600002Scopus ID: 2-s2.0-84971014023OAI: oai:DiVA.org:kth-189397DiVA: diva2:948162
Note

QC 20160708

Available from: 2016-07-08 Created: 2016-07-04 Last updated: 2017-11-28Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Tancer, Martin
By organisation
Mathematics (Dept.)
In the same journal
Israel Journal of Mathematics
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 6 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf