Open Collections

Shortest path embeddings of graphs on surfaces

Banff International Research Station for Mathematical Innovation and Discovery

The classical theorem of Fary states that every planar graph can be represented by an embedding in which every edge is represented by a straight line segment. We consider generalizations of Fary's theorem to surfaces equipped with Riemannian metrics. In this setting, we require that every edge is drawn as a shortest path between its two endpoints and we call an embedding with this property a shortest path embedding. The main question considered in the talk is whether given a closed surface \(S\), there exists a Riemannian metric for which every topologically embeddable graph admits a shortest path embedding. This question is also motivated by various problems regarding crossing numbers on surfaces. It is easy to observe that the round metrics on the sphere and the projective plane have this property. We provide flat metrics on the torus and the Klein bottle which also have this property. On the other hand the unit square flat metric on the Klein bottle there exists a graph without shortest path embeddings. For large \(g\), there exist graphs \(G\) embeddable into the orientable surface of genus \(g\), such that with large probability a random hyperbolic metric does not admit a shortest path embedding of \(G\) (w.r.t. the Weil-Petersson volume on moduli space). On the other hand, it is possible to construct a hyperbolic metric on every orientable surface \(S\) of genus \(g\), such that every graph embeddable into \(S\) can be embedded so that every edge is a concatenation of at most \(O(g)\) shortest paths. Joint with A. Hubard, V. Kaluza, A. de Mesmay.

Mathematics; Combinatorics; Computer science; Discrete mathematics

video/mp4

Author affiliation: Charles University in Prague

2018-04-12

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/65300

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/