View PDF HTML (experimental)

Abstract:We study the combinatorial structure of systems of unique shortest paths in real-weighted graphs. We say that such a path system is \emph{strongly metrizable}.
A folklore fact is that every strongly metrizable path system must be \emph{simple} and \emph{consistent}, meaning that it avoids paths that repeat nodes, and it also avoids the pattern where a pair of its paths intersect, split apart, and then intersect again later. Our contribution is to fully characterize strong metrizability via an expanded list of forbidden subsystems, beyond the two implied by simplicity and consistency. That is:
-- We define a new family of patterns that we call \emph{polyhedral pairs}, which are derived from 2-colored abstract polyhedra,
-- We prove that a directed path system is strongly metrizable via a directed graph if and only if it is simple, consistent, and it does not contain the nontrivial image of either side of an \emph{oriented} polyhedral pair as a subsystem,
-- We prove that an undirected path system is strongly metrizable via an undirected graph if and only if it is simple, consistent, and it does not contain the nontrivial image of either side of a \emph{non-oriented} polyhedral pair as a subsystem.
We also discuss some aesthetic structural properties that can be forced for these polyhedra, and we discuss improvements to the characterization that can be obtained in the directed acyclic setting.

Submission history

From: Greg Bodwin [view email]
[v1] Wed, 25 Apr 2018 18:28:06 UTC (57 KB)
[v2] Wed, 17 Oct 2018 17:12:56 UTC (56 KB)
[v3] Fri, 7 Aug 2026 22:51:28 UTC (164 KB)