Unknotted strand routings of triangulated meshes

Abdulmelik Mohammed, Mustafa Hajij

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

3 Citations (Scopus)
191 Downloads (Pure)


In molecular self-assembly such as DNA origami, a circular strand’s topological routing determines the feasibility of a design to assemble to a target. In this regard, the Chinese-postman DNA scaffold routings of Benson et al. (2015) only ensure the unknottedness of the scaffold strand for triangulated topological spheres. In this paper, we present a cubic-time 53−approximation algorithm to compute unknotted Chinese-postman scaffold routings on triangulated orientable surfaces of higher genus. Our algorithm guarantees every edge is routed at most twice, hence permitting low-packed designs suitable for physiological conditions.
Original languageEnglish
Title of host publicationDNA Computing and Molecular Programming
Subtitle of host publication23rd International Conference, DNA 23, Austin, TX, USA, September 24–28, 2017, Proceedings
EditorsRobert Brijder, Lulu Qian
ISBN (Electronic)978-3-319-66799-7
Publication statusPublished - 2017
MoE publication typeA4 Article in a conference publication
EventInternational Conference on DNA Computing and Molecular Programming - Austin, United States
Duration: 24 Sep 201729 Sep 2017
Conference number: 23

Publication series

Name Lecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceInternational Conference on DNA Computing and Molecular Programming
Abbreviated titleDNA
Country/TerritoryUnited States
Internet address


  • DNA nanotechnology
  • Graphs
  • Knots
  • DNA origami
  • Knot theory
  • Graph theory
  • Chinese postman problem


Dive into the research topics of 'Unknotted strand routings of triangulated meshes'. Together they form a unique fingerprint.

Cite this