Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
    
new.dli.ernet.in/rawdataupload/upload/insa/INSA_2/… may be of interest. –  Tony Huynh Nov 16 '13 at 2:41
2  
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
add comment

1 Answer 1

up vote 10 down vote accepted

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.

share|improve this answer
    
Thanks, Gjergji, for the useful connection to median graphs. –  Joseph O'Rourke Nov 16 '13 at 15:12
    
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
    
@JosephO'Rourke, yes, the two definitions give the same notion of extreme point. –  Gjergji Zaimi Nov 17 '13 at 3:12
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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