Determining Graph Hulls Consider the following undirected unweighted graph:

The green nodes separate the graph from the &quot;external environment&quot;. 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

Which is the fastest known algorithm to determine, given an undirected unweighted graph $G$, one of its hulls?
Is it possible that the number of hulls of a graph is superpolynomial in $|V|$?
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)?
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)?
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:


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