7
$\begingroup$

Consider the following undirected unweighted graph:

The green nodes constitute the hull

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:

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:

The blue nodes constitute 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)?
$\endgroup$
  • 10
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Mar 4 '11 at 14:28
  • 1
    $\begingroup$ @Tsuyoshi: Cool...I feel dumb. So, what if the drawing is required to be planar? $\endgroup$ – Giorgio Camerani Mar 4 '11 at 15:02
  • 5
    $\begingroup$ 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. $\endgroup$ – Hsien-Chih Chang 張顯之 Mar 4 '11 at 15:07
  • 1
    $\begingroup$ Does the "planar case" section of Wikipedia's Convex Hull Algorithms answer your question about plane drawings? $\endgroup$ – Aaron Sterling Mar 4 '11 at 15:07
  • 1
    $\begingroup$ Who downrated this question? The fact that an obvious answer exists doesn't make it necessarily bad. $\endgroup$ – Neil Mar 4 '11 at 15:11
6
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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