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

DOI10.1016/j.tcs.2019.03.019zbMath1425.68310arXiv1710.09048OpenAlexW2963190703WikidataQ128208437 ScholiaQ128208437MaRDI QIDQ2315018

Joanna A. Ellis-Monaghan, Mark N. Ellingham

Publication date: 31 July 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1710.09048

zbMATH Keywords

reporter strandDNA-origamiedge-outer embeddingone-face embeddingorientable graph embedding

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Protein sequences, DNA sequences (92D20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Design formalism for DNA self-assembly of polyhedral skeletons using rigid tiles

Cites Work

• Design tools for reporter strands and DNA origami scaffold strands
• On existence of reporter strands in DNA-based graph structures
• Unknotted strand routings of triangulated meshes
• DNA origami and the complexity of Eulerian circuits with turning costs
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Matching, Euler tours and the Chinese postman
• Graphs on Surfaces
• DNA origami and unknotted A-trails in torus graphs
• The Genus, Regional Number, and Betti Number of a Graph
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Edge-outer graph embedding and the complexity of the DNA reporter strand problem