# Geodesic convex hulls in a graph; and their properties

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!

-
new.dli.ernet.in/rawdataupload/upload/insa/INSA_2/… may be of interest. – Tony Huynh Nov 16 '13 at 2:41
It seems like the Hypercube graph $Q_n$ makes a nice example here. If I understand things correctly the convex sets correspond to subcubes ($k$ coordinates fixed, the remaining $n-k$ take on all possible values), the halfspaces (by your definition) correspond to subcubes of dimension $n-1$, and it's natural then to think of a convex set as the intersection of halfspaces. – Kevin P. Costello Nov 16 '13 at 5:45
@TonyHuynh: Thanks. That Sampathkumar paper defines convexity to include all vertices on any path between two nodes, rather than just those on shortest paths. – Joseph O'Rourke Nov 16 '13 at 14:54

There is quite a bit of literature on convexity for graphs. One can basically ask to translate any classical convexity result to this new setting. Suppose for example you consider a vertex $v\in S$ to be an extreme point of the convex set $S\subset G$, if $S/\lbrace v\rbrace$ is also convex. Then the class of graphs for which every convex set is the convex hull of its extreme points is precisely the class of chordal graphs without induced $3$-fans. This was proved in "Convexity in graphs and hypergraphs" by M. Farber, R.E. Jamison (SIAM J. Algebraic Discrete Math., 7 (1986), pp. 433–444). This paper will probably also provide a good starting point for exploring the literature.
And now thanks for the edit describing how to identify extreme points! I was thinking of requiring that $CH(S \setminus \{v\})$ have smaller cardinality than $CH(S)$. Maybe the two definitions are equivalent... – Joseph O'Rourke Nov 17 '13 at 0:39