2
$\begingroup$

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).


     CHGraph
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!

$\endgroup$
3
  • $\begingroup$ new.dli.ernet.in/rawdataupload/upload/insa/INSA_2/… may be of interest. $\endgroup$
    – Tony Huynh
    Nov 16, 2013 at 2:41
  • 2
    $\begingroup$ 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. $\endgroup$ Nov 16, 2013 at 5:45
  • $\begingroup$ @TonyHuynh: Thanks. That Sampathkumar paper defines convexity to include all vertices on any path between two nodes, rather than just those on shortest paths. $\endgroup$ Nov 16, 2013 at 14:54

1 Answer 1

10
$\begingroup$

One particular class of graphs where this notion of convexity is used is that of median graphs. In this context one can make sense of halfspaces as you described and even carry over some analogs of certain theorems about convex sets, such as Helly's theorem. This isn't far from Kevin's comment because such graphs are retracts of hypercubes.

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.

$\endgroup$
3
  • $\begingroup$ Thanks, Gjergji, for the useful connection to median graphs. $\endgroup$ Nov 16, 2013 at 15:12
  • $\begingroup$ 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... $\endgroup$ Nov 17, 2013 at 0:39
  • $\begingroup$ @JosephO'Rourke, yes, the two definitions give the same notion of extreme point. $\endgroup$ Nov 17, 2013 at 3:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.