There are a whole range of problems that graph theory can be applied. Just the tip of the iceberg below.
Study of genome rearrangements. Sorting the most parsimonious genome rearrangement scenario requires resolving breakpoint graph. See work in comparing mammalian genomes.
Structure prediction of RNAs and proteins. Adjancency of residues in RNA or protein structures can be described in contact graph. In addition, graph decomposition is used to solve modular components or motifs (for example, pseudoknot).
Graph-based clustering. This can be useful for finding motifs in protein-protein interaction network or protein families in sequence similarity graph. Some tools (e.g. MCL) can generate motifs or clusters by simulating flows inside the network.
Graph layout algorithm can be used to visualize large-scale metabolic pathway or phylogenetic trees/networks.
Many other bioinformatics problems can be conceptually reduced to graph representations. Graph traversal, coloring, clique enumeration, matching, flow, minimum spanning tree, shortest path etc. can then be used to solve miscellaneous problems.
Any problem that involves atoms and bonds in bioinformatics are solved using graph theory. So, anything to do with force fields (Molecular Dynamics, Molecular Modeling), comparing molecular structures (metabolite identification, enzyme reaction mechanisms), etc, etc are all solved with (chemical) graph theory.
These graph theory use cases are so common, you would not even call them popular anymore.
Some of the interesting publications you can look:
Isoform specific expression estimation from RNA-Seq data uses graph theory.
Splicing graph analysis of pre-mRNA splicing can also be reduced to a graph problem. The exons in a gene can be thought of nodes and their splicing partners can be thought of as edges.