Geodesic Geometry on Graphs

We investigate a graph theoretic analog of geodesic geometry. In a graph G = ( V , E ) we consider a system of paths P = { P u , v : u , v ∈ V } where P u , v connects vertices u and  v . This system is consistent in that if vertices y ,  z are in P u , v , then the subpath of P u , v between them c...

Full description

Saved in:
Bibliographic Details
Published in:Discrete & computational geometry 2022-07, Vol.68 (1), p.298-347
Main Authors: Cizma, Daniel, Linial, Nati
Format: Article
Language:English
Subjects:
Apexes
Combinatorics
Computational Mathematics and Numerical Analysis
Differential geometry
Geometry
Graphs
Mathematics
Mathematics and Statistics
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We investigate a graph theoretic analog of geodesic geometry. In a graph G = ( V , E ) we consider a system of paths P = { P u , v : u , v ∈ V } where P u , v connects vertices u and  v . This system is consistent in that if vertices y ,  z are in P u , v , then the subpath of P u , v between them coincides with P y , z . A map w : E → ( 0 , ∞ ) is said to induce P if for every u , v ∈ V the path P u , v is w -geodesic. We say that G is metrizable if every consistent path system is induced by some such  w . As we show, metrizable graphs are very rare, whereas there exist infinitely many 2-connected metrizable graphs.
ISSN:0179-5376
1432-0444
DOI:10.1007/s00454-021-00345-w