In recent years, especially after the completion of genome sequencing projects for various organisms, there has been a growing interest in the study of regulation and gene expression mechanisms. The amount of data available makes it unfeasible to pursue a manual analysis calling for some sort of automatic processing. In this context, bioinformatics tools have become more and more central to the activity of biologists. Despite the remarkable success of these tools in some areas of application like gene finding, sequence alignment, etc, there are still problems for which no significant results have been achieved. Notably, the identification of biologically meaningful motifs in cis-regulatory regions remains an open problem. However, many approaches have been proposed and one can find a panoply of published papers describing novel algorithms to address the problem. These algorithms can be roughly classified in two main groups: combinatorial and statistical. In this survey we will concentrate on a specific sub-group of combinatorial algorithms: algorithms based on graph theory. This interest is chiefly motivated by the fact that some recent proposals using this approach have claimed to gain efficiency by avoiding unnecessary explorations of the search space. Furthermore, we will compare their efficiency and operation with other combinatorial algorithms which use other data structures.