For an undirected connected graph, we associate a lattice, that we call the Laplacian lattice of the graph. We describe the Voronoi diagram of this lattice under a certain simplicial distance function and show that the properties of this Voronoi diagram can be used to derive structural results on graphs. For ex. Riemann-Roch theorem for graphs. We also discuss some applications to algorithmic and classification problems.