There are a whole range of problems that graph theory can be applied. Just the tip of the iceberg below.

Genome assembly. Graph theory is used in generations of assembly softwares, in the form of overlap graph and de brujin graph. See introductory slides here and here, respectively.

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).

Graphbased clustering. This can be useful for finding motifs in proteinprotein 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 largescale 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:
Prediction of functional sites in proteins using conserved functional group analysis.
A graphtheory algorithm for rapid protein sidechain prediction.
Improved microarraybased decision support with graph encoded interactome data.
Recent review: Building a parallel between structural and topological properties.
Isoform specific expression estimation from RNASeq data uses graph theory.
Splicing graph analysis of premRNA 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.