# Determining Graph Hulls

Consider the following undirected unweighted graph:

The green nodes separate the graph from the "external environment". Let's call them the graph hull. Now, a graph may have several hulls. Consider the following graph, where the green nodes constitute the hull:

If we rearrange the drawing in the following way (stretching the blue nodes to the outside) then the blue nodes become the hull:

Questions

1. Which is the fastest known algorithm to determine, given an undirected unweighted graph $$G$$, one of its hulls?
2. Is it possible that the number of hulls of a graph is superpolynomial in $$|V|$$?
3. Which is the fastest known algorithm to determine, given an undirected unweighted graph $$G$$, its minimum hull (i.e. the hull having the minimum number of vertices)?
4. Which is the fastest known algorithm to determine, given an undirected unweighted graph $$G$$, its maximum hull (i.e. the hull having the maximum number of vertices)?
• Judging from the first figure, it seems that you do not require the drawing to be planar. In that case, every cycle is a “hull,” and this observation gives answers to your four questions. Mar 4 '11 at 14:28
• @Tsuyoshi: Cool...I feel dumb. So, what if the drawing is required to be planar? Mar 4 '11 at 15:02
• If the drawing is planar, then a hull must be a face under some embedding of the graph. Then I guess all the problems can be solved in linear time. Mar 4 '11 at 15:07
• Does the "planar case" section of Wikipedia's Convex Hull Algorithms answer your question about plane drawings? Mar 4 '11 at 15:07
• Who downrated this question? The fact that an obvious answer exists doesn't make it necessarily bad.
– Neil
Mar 4 '11 at 15:11

This question turned out to be trivial. As Lev Reyzin said in his comment, the answer was already encoded in the figures. I should have watched them more carefully...Of course, looking at the figures, it was already evident that those hulls are cycles. What was not immediately evident to me is the obvious fact that given whatever drawing like those, you could pick whatever cycle in it (even a 3-cycle), "enlarge" it, and "throw" all the remaining nodes inside it, thus obtaining a hull. So:

1. As Tsuyoshi Ito pointed out, if the drawing is not requested to be planar, then every cycle is a hull, and this observation simultaneously answers all the four questions I've posted.
2. As Hsien-Chih Chang and Peter Shor indicated, if the drawing is requested to be planar, then the questions can be answered by using planar graph embedding algorithms.

Finally, to make things worse, it seems that the choice of the term "hull" was unfortunate: the correct term to indicate what I had in mind is "outer face" (although such term is probably meaningless for non-planar graphs).

• you should accept this answer so the question doesn't keep popping up every month or so Mar 5 '11 at 7:06
• @Suresh: I've tried to accept it, but the system said: "You can accept your own answer in 2 days". Mar 5 '11 at 8:36
• I think that as long as the answer has positive votes, the question won't keep popping up. Mar 5 '11 at 13:06