Edge-outer graph embedding and the complexity of the DNA reporter strand problem

In 2009, Jonoska, Seeman and Wu showed that every graph admits a route for a DNA reporter strand, that is, a closed walk covering every edge either once or twice, in opposite directions if twice, and passing through each vertex in a particular way. This corresponds to showing that every graph has an...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2019-09, Vol.785, p.117-127
Main Authors: Ellingham, M.N., Ellis-Monaghan, Joanna A.
Format: Article
Language:English
Subjects:
DNA origami
Edge-outer embedding
One-face embedding
Orientable graph embedding
Reporter strand
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In 2009, Jonoska, Seeman and Wu showed that every graph admits a route for a DNA reporter strand, that is, a closed walk covering every edge either once or twice, in opposite directions if twice, and passing through each vertex in a particular way. This corresponds to showing that every graph has an edge-outer embedding, that is, an orientable embedding with some face that is incident with every edge. In the motivating application, the objective is such a closed walk of minimum length. Here we give a short algorithmic proof of the original existence result, and also prove that finding a shortest length solution is NP-hard, even for 3-connected cubic (3-regular) planar graphs. Independent of the motivating application, this problem opens a new direction in the study of graph embeddings, and we suggest several problems emerging from it.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2019.03.019