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.).
2013 (English)In: Graph Drawing: 21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers, Springer, 2013, 472-483 p.Conference paper, Published paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
Springer, 2013. 472-483 p.
Series
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743 ; 8242 LNCS
Keyword [en]
Curves on 2-manifolds, Lickorish's theorem, Simultaneous planar drawings
National Category
Other Mathematics Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-141003Scopus ID: 2-s2.0-84891862406OAI: oai:DiVA.org:kth-141003DiVA: diva2:693761
Conference
21st International Symposium on Graph Drawing, GD 2013; Bordeaux; France; 23 September 2013 through 25 September 2013
Note

QC 20140205

Available from: 2014-02-05 Created: 2014-02-05 Last updated: 2017-04-28Bibliographically approved

Open Access in DiVA

No full text

Scopus

Search in DiVA

By author/editor
Tancer, Martin
By organisation
Mathematics (Dept.)
Other MathematicsComputer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 22 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