Recent advances in DNA self-assembly have resulted in increasingly sophisticated nanoscale wire-frame structures that can be modeled by graphs. These constructs serve emergent applications in biomolecular computing, nanoelectronics, biosensors, drug delivery systems, and organic synthesis. One construction method uses k-armed branched junction molecules, called tiles, whose arms are double strands of DNA with one strand extending beyond the other, forming a ‘sticky end’ at the end of the arm that can bond to any other sticky end with complementary Watson-Crick bases. A vertex of degree k in the target graph is formed from a k-armed tile, and joined sticky ends form the edges. We use graph theory to determine optimal design strategies for scientists producing these nanostructures. This includes computational complexity results, algorithms, and pragmatic approaches for special classes of graphs, as well as new mathematical theory and new graphs invariants.