English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In 2009, Jonoska, Seeman and Wu showed that every graph admits a route for aDNA reporter strand, that is, a closed walk covering every edge either once ortwice, in opposite directions if twice, and passing through each vertex in aparticular way. This corresponds to showing that every graph has an\emph{edge-outer embedding}, that is, an orientable embedding with some facethat is incident with every edge. In the motivating application, the objectiveis such a closed walk of minimum length. Here we give a short algorithmic proofof the original existence result, and also prove that finding a shortest lengthsolution is NP-hard, even for $3$-connected cubic ($3$-regular) planar graphs.Independent of the motivating application, this problem opens a new directionin the study of graph embeddings, and we suggest new problems emerging from it.

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