Articulo
Tree loop graphs
Autor
Alcón, Liliana Graciela
Cerioli, Márcia R.
Figueiredo, Celina M. H. de
Gutiérrez, Marisa
Meidanis, João
Institución
Resumen
Many problems involving DNA can be modeled by families of intervals. However, traditional interval graphs do not take into account the repeat structure of a DNA molecule. In the simplest case, one repeat with two copies, the underlying line can be seen as folded into a loop. We propose a new definition that respects repeats and define loop graphs as the intersection graphs of arcs of a loop. The class of loop graphs contains the class of interval graphs and the class of circular-arc graphs. Every loop graph has interval number 2. We characterize the trees that are loop graphs. The characterization yields a polynomial-time algorithm which given a tree decides whether it is a loop graph and, in the affirmative case, produces a loop representation for the tree. Facultad de Ciencias Exactas