We provide a complete description of important geometric invariants of the Laplacian lattice of a multigraph under the distance function induced by a regular simplex, namely Voronoi Diagram, Delaunay Triangulation, Delaunay Polytope and its combinatorial structure, Shortest Vectors, Covering and Packing Radius. We use this information to obtain the following results: i. Every multigraph defines a Delaunay triangulation of its Laplacian lattice and this Delaunay triangulation contains complete information of the multigraph up to isomorphism. ii. The number of multigraphs with a given Laplacian lattice is controlled, in particular upper bounded, by the number of different Delaunay triangulations. iii. We obtain formulas for the covering and packing densities of a Laplacian lattice and deduce that in the space of Laplacian lattices of undirected connected multigraphs, the Laplacian lattices of highly connected multigraphs such as Ramanujan multigraphs possess good covering and packing properties.
ii. The Delaunay triangulation under the simplicial distance function provides more refined information on the underlying (connected) multigraph and in fact characterizes the multigraph completely up to isomorphism. On the other hand in the Euclidean case such an analogue is true only for three-connected graphs. A weaker result is known for general connected graphs @cite_0 .
@cite_0
1794573077
Algebraic curves have a discrete analog in finite graphs. Pursuing this analogy, we prove a Torelli theorem for graphs. Namely, we show that two graphs have the same Albanese torus if and only if the graphs obtained from them by contracting all separating edges are 2-isomorphic. In particular, the strong Torelli theorem holds for 3-connected graphs. Next, using the correspondence between compact tropical curves and metric graphs, we prove a tropical Torelli theorem giving necessary and sufficient conditions for two tropical curves to have the same principally polarized tropical Jacobian. By contrast, we prove that, in a suitably defined sense, the tropical Torelli map has degree one. Finally, we describe some natural posets associated to a graph and prove that they characterize its Delaunay decomposition.