Shortest path embeddings of graphs on surfaces
From MaRDI portal
Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Planar graphs; geometric and topological aspects of graph theory (05C10) Global geometric and topological methods (à la Gromov); differential geometric analysis on metric spaces (53C23)
Abstract: The classical theorem of F'{a}ry 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 F'{a}ry'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 addressed in this paper 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. We 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. Then we show that for the unit square flat metric on the Klein bottle there exists a graph without shortest path embeddings. We show, moreover, that 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, where the probability measure is proportional to the Weil-Petersson volume on moduli space. Finally, we 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.
Recommendations
Cites work
- scientific article; zbMATH DE number 2182144 (Why is no real title available?)
- scientific article; zbMATH DE number 52737 (Why is no real title available?)
- scientific article; zbMATH DE number 2070189 (Why is no real title available?)
- scientific article; zbMATH DE number 1500678 (Why is no real title available?)
- scientific article; zbMATH DE number 2103273 (Why is no real title available?)
- scientific article; zbMATH DE number 7581723 (Why is no real title available?)
- scientific article; zbMATH DE number 3047038 (Why is no real title available?)
- A primer on mapping class groups
- An infinite set of torus triangulations of connectivity 5 whose graphs are not uniquely embeddable in the torus
- Computing a canonical polygonal schema of an orientable triangulated surface
- Crossing numbers of graph embedding pairs on closed surfaces
- Filling Riemannian manifolds
- Foundations of Hyperbolic Manifolds
- Graphs on surfaces
- Growth of Weil-Petersson volumes and random hyperbolic surface of large genus
- How to Draw a Graph
- How to change a triangulation of a surface into a geodesic triangulation?
- Irreducible triangulations of the Klein bottle
- Note on the irreducible triangulations of the Klein bottle
- On Embedding a Graph in the Grid with the Minimum Number of Bends
- On the period matrix of a Riemann surface of large genus (with an appendix by J. H. Conway and N. J. A. Sloane)
- One-to-one piecewise linear mappings over triangulations
- Optimal pants decompositions and shortest homotopic cycles on an orientable surface
- Pants decompositions of random surfaces
- Random construction of Riemann surfaces
- Simultaneous Embedding of Planar Graphs with Few Bends
- The graph crossing number and its variants: a survey
- Tightening nonsimple paths and cycles on surfaces
- Two maps on one surface
- Two maps with large representativity on one surface
Cited in
(9)- scientific article; zbMATH DE number 7111090 (Why is no real title available?)
- Shortest path embeddings of graphs on surfaces
- Minimal Delaunay triangulations of hyperbolic surfaces
- Holiest minimum-cost paths and flows in surface graphs
- Low-dimensional topology. Abstracts from the workshop held January 15--21, 2023
- Stable embeddings on closed surfaces with respect to the minimum length
- scientific article; zbMATH DE number 6783474 (Why is no real title available?)
- Short topological decompositions of non-orientable surfaces
- Embedding of metric graphs on hyperbolic surfaces
This page was built for publication: Shortest path embeddings of graphs on surfaces
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1688859)
