We demonstrate the effectiveness of prime graphs for the calculation of the (Castelnuovo-Mumford) regularity of graphs. Such a notion allows us to reformulate the regularity as a generalized induced matching problem and perform regularity calculations in specific graph classes, including (C-3; P-5)-free graphs, P-6-free bipartite graphs and all Cohen-Macaulay graphs of girth at least five. In particular, we verify that the five cycle graph C-5 is the unique connected graph satisfying the inequality im(G) < reg(G) = m(G). In addition, we prove that, for each integer n >= 1, there exists a vertex decomposable perfect prime graph G(n) with reg(G(n)) = n.