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)?
Improve this question
$\endgroup$
17
  • 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, 2011 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, 2011 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, 2011 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, 2011 at 15:07
  • 2
    $\begingroup$ Who downrated this question? The fact that an obvious answer exists doesn't make it necessarily bad. $\endgroup$
    – Neil
    Mar 4, 2011 at 15:11

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$
3
  • $\begingroup$ you should accept this answer so the question doesn't keep popping up every month or so $\endgroup$
    – Suresh Venkat
    Mar 5, 2011 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, 2011 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, 2011 at 13:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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