On the number of cut locus structures on graphs

We proved in another paper that every connected graph can be realized as the cut locus of some point on some riemannian surface. Here we give upper bounds on the number of such realizations.