Unknotted strand routings of triangulated meshes

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


Research units

  • University of South Florida


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
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
CountryUnited States
Internet address

    Research areas

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

Download statistics

No data available

ID: 15985174