Tree Loop Graphs

Many problems involving DNA can be modelled by interval families. However, traditional interval graphs do not take into account the repeat structures of a DNA molecule. 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, it produces a loop representation for the tree.