A novel graph seriation method based random graph theory is proposed in this paper. By seriation processing, graphs can be converted to string through constructing toroidal catch digraph. Seriated graph distance is using to represent the similarity between graphs. It measures the structural differences between graphs based on the dynamic warping technique. Dynamic Time Warping distance used in the paper is evaluated by dynamic programming. The results of our experiments demonstrate that the proposed method is eligible for graph distance measure.