Designing self-assembling DNA nanostructures often requires the identification of a route for a scaffolding strand of DNA through the target structure. When the target structure is modeled as a graph, these scaffolding routes correspond to Eulerian circuits subject to turning restrictions imposed by physical constraints on the strands of DNA. Existence of such Eulerian circuits is an NP-hard problem, which can be approached by adapting solutions to a version of the Traveling Salesperson Problem. However, the author and collaborators have demonstrated that even Eulerian circuits obeying these turning restrictions are not necessarily feasible as scaffolding routes by giving examples of nontrivially knotted circuits which cannot be traced by the unknotted scaffolding strand. Often, targets of DNA nanostructure self-assembly are modeled as graphs embedded on surfaces in space. In this case, Eulerian circuits obeying the turning restrictions correspond to A-trails, circuits which turn immediately left or right at each vertex. In any graph embedded on the sphere, all A-trails are unknotted regardless of the embedding of the sphere in space. We show that this does not hold in general for graphs on the torus. However, we show this property does hold for checkerboard-colorable graphs on the torus, that is, those graphs whose faces can be properly 2-colored, and provide a partial converse to this result. As a consequence, we characterize (with one exceptional family) regular triangulations of the torus containing unknotted A-trails. By developing a theory of sums of A-trails, we lift constructions from the torus to arbitrary n-tori, and by generalizing our work on A-trails to smooth circuit decompositions, we construct all torus links and certain sums of torus links from circuit decompositions of rectangular torus grids. Graphs embedded on surfaces are equivalent to ribbon graphs, which are particularly well-suited to modeling DNA nanostructures, as their boundary components correspond to strands of DNA and their twisted ribbons correspond to double-helices. Every ribbon graph has a corresponding delta-matroid, a combinatorial object encoding the structure of the ribbon-graph's spanning quasi-trees (substructures having exactly one boundary component). We show that interlacement with respect to quasi-trees can be generalized to delta-matroids, and use the resulting structure on delta-matroids to provide feasible-set expansions for a family of delta-matroid polynomials, both recovering well-known expansions of this type (such as the spanning-tree expansion of the Tutte polynnomial) as well as providing several previously unknown expansions. Among these are expansions for the transition polynomial, a version of which has been used to study DNA nanostructure self-assembly, and the interlace polynomial, which solves a problem in DNA recombination.

A model for DNA recombination uses 4-valent rigid vertex graphs, called assembly graphs. An assembly graph, similarly to the projection of knots, can be associated with an unsigned Gauss code, or double occurrence word. We define biologically motivated reductions that act on double occurrence words and, in turn, on their associated assembly graphs. For every double occurrence word w there is a sequence of reduction operations that may be applied to w so that what remains is the empty word, [epsilon]. Then the nesting index of a word w, denoted by NI(w), is defined to to be the least number of reduction operations necessary to reduce w to [epsilon]. The nesting index is the first property of assembly graphs that we study. We use chord diagrams as tools in our study of the nesting index. We observe two double occurrence words that correspond to the same circle graph, but that have arbitrarily large differences in nesting index values. In 2012, Buck et al. considered the cellular embeddings of assembly graphs into orientable surfaces. The genus range of an assembly graph [Gamma], denoted gr([Gamma]), was defined to be the set of integers g where g is the genus of an orientable surface F into which [Gamma] cellularly embeds. The genus range is the second property of assembly graphs that we study. We generalize the notion of the genus range to that of the genus spectrum, where for each g [isin] gr([Gamma]) we consider the number of orientable surfaces F obtained from [Gamma] by a special construction, called a ribbon graph construction, that have genus g. By considering this more general notion we gain a better understanding of the genus range property. Lastly, we show how one can obtain the genus spectrum of a double occurrence word from the genus spectrums of its irreducible parts, i.e., its double occurrence subwords. In the final chapter we consider constructions of double occurrence words that recognize certain values for nesting index and genus range. In general, we find that for arbitrary values of nesting index [ge] 2 and genus range, there is a double occurrence word that recognizes those values.

Using the orbicell decomposition of the Deligne-Mumford compactification of the moduli space of Riemann surfaces studied before by the author, a chain complex based on semistable ribbon graphs is constructed which is an extension of the Konsevich’s graph homology. / En este trabajo mediante la descomposicion orbicelular de la compacticacion de Deligne-Mumford del espacio de moduli de supercies de Riemann (estudiada antes por el autor) construimos un complejo basado en grafos de cinta semiestables, lo cual constituye una extension de la homologa de grafos de Kontsevich.