The \emph{isometric path antichain cover number} of a graph $G$, denoted by $ipacc(G)$, is a graph parameter that was recently introduced to provide a constant factor approximation algorithm for \textsc{Isometric Path Cover}, whose objective is to cover all vertices of a graph with a minimum number of isometric paths (i.e. shortest paths between their end-vertices). This parameter was previously shown to be bounded for chordal graphs and, more generally, for graphs of bounded \emph{chordality} and bounded \emph{treelength}. In this paper, we show that the isometric path antichain cover number remains bounded for graphs in three seemingly unrelated graph classes, namely, \emph{hyperbolic graphs}, \emph{(theta, prism, pyramid)-free graphs}, and \emph{outerstring graphs}. Hyperbolic graphs are extensively studied in \emph{Metric Graph Theory}. The class of (theta, prism, pyramid)-free graphs are extensively studied in \emph{Structural Graph Theory}, \textit{e.g.} in the context of the \emph{Strong Perfect Graph Theorem}. The class of outerstring graphs is studied in \emph{Geometric Graph Theory} and \emph{Computational Geometry}. Our results imply a constant factor approximation algorithm for \textsc{Isometric Path Cover} on all the above graph classes. Our results also show that the distance functions of these (structurally) different graph classes are more similar than previously thought.

Thanks. We have received your report. If we find this content to be in
violation of our guidelines,
we will remove it.

Ok