Determining Graph Hulls
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).