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!