# 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. – Tsuyoshi Ito Mar 4 '11 at 14:28
• @Tsuyoshi: Cool...I feel dumb. So, what if the drawing is required to be planar? – Giorgio Camerani 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. – Hsien-Chih Chang 張顯之 Mar 4 '11 at 15:07
• Does the "planar case" section of Wikipedia's Convex Hull Algorithms answer your question about plane drawings? – Aaron Sterling 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