This question asks for an analog of the convex hull in a graph that parallels (as far as possible) convex sets in Euclidean space.
Let $G$ be a simple, undirected graph, and let $S \subseteq V$ be a subset of its vertices. Use geodesic as synonymous with shortest path, where distance is measured by the number of edges in a path.
I would like to define the convex hull $CH(S)$ as the set of vertices of $G$ produced by the following process. $S$ is in $CH(S)$. For each $x,y \in CH(S)$, all the vertices along (all) the geodesics between $x$ and $y$ are included in $CH(S)$. Etc.: For every pair of vertices in $CH(S)$, all the vertices on the geodesics between these pairs are thrown into $CH(S)$, until $CH(S)$ stabilizes.
As an example, consider the graph $G$ depicted below, with $S=\{1,2,9\}$ (left). What is the convex hull $CH(S)$ of $\{1,2,9\}$? It must include all the vertices on the geodesics from $1$ to $2$: $(1,7,3,2)$; and the geodesics from $2$ to $9$: $(2,12,9)$; and the geodesics from $1$ to $9$: $(1,7,8,9)$ and $(1,6,5,9)$—NB: two of equal length. So it must include $\{1,2,3,5,6,7,8,9,12\}$ (right).
Now I would like these properties for the convex-hull definition:
(1) Any geodesic in $G$ meets $CH(S)$ in a segment, a single connected path. For example, the unique geodesic from $1$ to $11$ meets $CH(1,2,9)$ in the single point $\mathbf{1}$, which is a segment. Another example is the geodesics between $4$ and $14$: $(14,13,\mathbf{12,9,8},10,11,4)$ or $(14,13,\mathbf{12,9,5,6,1},4)$. I believe this holds; I could sketch a proof...
(2) $CH(S)$ can be viewed as the intersection of the halfspaces determining the boundary of $CH(S)$. Here I am having difficulty coming up with a definition of halfspace that makes sense in this context, and shows that $CH(S)$ is the intersection of halfspaces. I want to say something like, "a set of vertices $S$ constitutes a halfspace if both $S$ and its complement in $G$ are convex."
(3) I think the latter uncertainty derives from the uncertainty how to define what should serve as an extreme point of $CH(S)$. Is there a natural definition?
I sense that I am reinventing a wheel turned over and over by many researchers before me. If that is the case, pointers would be welcomed! Thanks!