We define well-founded rewrite orderings on graphs and show that they can be used to show termination of graph rewrite rules by checking all (infinitely many) cyclic extensions of a given set of graph rewrite rules. We then introduce an ordering on graphs inspired by the recursive path ordering on terms. We show that our graph path ordering is a well-founded rewrite ordering on graphs for which checking termination of a finite set of graph rewrite rules is decidable. Our graph path ordering applies to arbitrary finite, directed, labelled, ordered multigraphs and provides therefore a building block for rewriting with such graphs, which should impact the many areas in which computations take place on graphs.