In this paper, we propose a new framework to characterize the electrohysterographic (EHG) signals recorded during pregnancy and labor. The approach is based on the analysis of the propagation of the uterine electrical activity. The processing pipeline includes i) the estimation of the statistical dependencies between the different recorded EHG signals, ii) the characterization of the obtained connectivity matrices using network measures and iii) the use of these measures in clinical application: the classification between pregnancy and labor. Due to its robustness to volume conductor, we used the imaginary part of coherence in order to produce the connectivity matrix which is then transformed into a graph. We evaluate the performance of several graph measures. We also compare the results with the parameter mostly used in the literature: the peak frequency combined with the propagation velocity (PV +PF). Our results show that the use of the network measures is a promising tool to classify labor and pregnancy contractions with a small superiority of the graph strength over PV+PF.