<p>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:</p>

<ol>
<li>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.</li>
<li>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.</li>
</ol>

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

CC BY-SA 2.5
2011-03-05T07:06:32.800Z
you should accept this answer so the question doesn't keep popping up every month or so
Suresh Venkat
CC BY-SA 2.5
2011-03-05T08:36:48.317Z
@Suresh: I've tried to accept it, but the system said: "You can accept your own answer in 2 days".
Giorgio Camerani
CC BY-SA 2.5
2011-03-05T13:06:13.813Z
I think that as long as the answer has positive votes, the question won't keep popping up.
Peter Shor 
CC BY-SA 2.5
2011-03-04T19:54:29.500Z
2011-03-05T12:51:11.503Z
2011-03-05T12:51:11.503Z
Giorgio Camerani
<p>Consider the following undirected unweighted graph:<br><br>
<img src="https://i.sstatic.net/67Dt0.jpg" alt="The green nodes constitute the hull" />
<br><br>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:
<br><br>
<img src="https://i.sstatic.net/Jy4ip.jpg" alt="The green nodes constitute the hull" />
<br><br>
If we rearrange the drawing in the following way (stretching the blue nodes to the outside) then the blue nodes become the hull:
<br><br>
<img src="https://i.sstatic.net/nPANe.jpg" alt="The blue nodes constitute the hull" />
<br><br></p>
<blockquote>
<p><b>Questions</b></p>
<ol>
<li>Which is the fastest known algorithm to determine, given an undirected unweighted graph <span class="math-container">$G$</span>, one of its hulls?</li>
<li>Is it possible that the number of hulls of a graph is superpolynomial in <span class="math-container">$|V|$</span>?</li>
<li>Which is the fastest known algorithm to determine, given an undirected unweighted graph <span class="math-container">$G$</span>, its minimum hull (i.e. the hull having the minimum number of vertices)?</li>
<li>Which is the fastest known algorithm to determine, given an undirected unweighted graph <span class="math-container">$G$</span>, its maximum hull (i.e. the hull having the maximum number of vertices)?</li></ol>
</blockquote>

CC BY-SA 2.5
2011-03-04T14:28:51.673Z
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
CC BY-SA 2.5
2011-03-04T15:02:17.403Z
@Tsuyoshi: Cool...I feel dumb. So, what if the drawing is required to be planar?
Giorgio Camerani
CC BY-SA 2.5
2011-03-04T15:07:12.813Z
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 張顯之
CC BY-SA 2.5
2011-03-04T15:07:37.023Z
Does the "planar case" section of Wikipedia's [Convex Hull Algorithms](http://en.wikipedia.org/wiki/Convex_hull_algorithms) answer your question about plane drawings?
Aaron Sterling
CC BY-SA 2.5
2011-03-04T15:11:46.357Z
Who downrated this question?  The fact that an obvious answer exists doesn't make it necessarily bad.
Neil
CC BY-SA 2.5
2011-03-04T15:27:15.260Z
@All: Let me clarify that the nodes I have do not have coordinates. I do not have a set of points in the Cartesian plane: what I have is only a set of edges.
Giorgio Camerani
CC BY-SA 2.5
2011-03-04T15:51:13.120Z
By "hull" do you mean "outer face"? I assume so. This question can be solved by planar graph embedding algorithms, but I'm not going to go into the details as they're a little complicated. If by "hull" you mean "convex hull," I think this question becomes more complicated.
Peter Shor 
CC BY-SA 2.5
2011-03-04T16:04:01.000Z
@Peter Shor: Yes right, by "hull" I meant "outer face".
Giorgio Camerani
CC BY-SA 2.5
2011-03-04T16:38:09.547Z
@Neil I downvoted this question. I thought it wasn't clear w/o the figures and that the figures made the answer obvious...
Lev Reyzin
CC BY-SA 2.5
2011-03-04T17:51:23.957Z
Sure any $K_4$ minor works, assuming you mean the obvious generalization.
Lev Reyzin
CC BY-SA 2.5
2011-03-04T18:13:18.193Z
@Walter: Now that the problem has been solved, could you perhaps write a short answer and accept it?
Jukka Suomela
CC BY-SA 2.5
2011-03-04T18:38:58.380Z
@Jukka: Should I write an answer to my own question? Maybe @Tsuyoshi could transform his comment in a lapidary answer to this ah-so-dumb question, and I'll accept it.
Giorgio Camerani
CC BY-SA 2.5
2011-03-04T18:51:11.040Z
@Peter of course it's always possible to make any face of a planar graph the outer face and convex
Suresh Venkat
CC BY-SA 2.5
2011-03-04T18:56:37.307Z
@Suresh: I agree. But if you want to solve the convex hull question completely, you have to show you can make any subset of a face of a planar graph the convex hull. I think you should be able to do this as well, but couldn't come up with a proof in the few minutes I was thinking about it.
Peter Shor 
CC BY-SA 2.5
2011-03-04T18:59:05.250Z
@Jukka: Let me clarify that I've nothing against answering my own question. It just seems curious (especially if the answer came from another person).
Giorgio Camerani
CC BY-SA 2.5
2011-03-04T19:29:16.073Z
As far as I am concerned, it is fine for you to post an answer.  I only happened to post the comment first.
Tsuyoshi Ito
<cc.complexity-theory><ds.algorithms><graph-theory><graph-algorithms>
Determining Graph Hulls
Giorgio Camerani
# Determining Graph Hulls

(Asked by: username_0 on 2011-03-04)

Consider the following undirected unweighted graph:  
  
![The green nodes constitute the hull](https://i.sstatic.net/67Dt0.jpg)
  
  
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](https://i.sstatic.net/Jy4ip.jpg)
  
  
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](https://i.sstatic.net/nPANe.jpg)

> **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)?

**Tags:** cc.complexity-theory, ds.algorithms, graph-theory, graph-algorithms

> **Comments:**
> **username_1**: 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.  
> **username_0**: @Tsuyoshi: Cool...I feel dumb. So, what if the drawing is required to be planar?  
> **username_2**: 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.  
> **username_3**: Does the "planar case" section of Wikipedia's [Convex Hull Algorithms](http://en.wikipedia.org/wiki/Convex_hull_algorithms) answer your question about plane drawings?  
> **username_4**: Who downrated this question?  The fact that an obvious answer exists doesn't make it necessarily bad.  
> **username_0**: @All: Let me clarify that the nodes I have do not have coordinates. I do not have a set of points in the Cartesian plane: what I have is only a set of edges.  
> **username_5**: By "hull" do you mean "outer face"? I assume so. This question can be solved by planar graph embedding algorithms, but I'm not going to go into the details as they're a little complicated. If by "hull" you mean "convex hull," I think this question becomes more complicated.  
> **username_0**: @Peter Shor: Yes right, by "hull" I meant "outer face".  
> **username_6**: @username_4 I downvoted this question. I thought it wasn't clear w/o the figures and that the figures made the answer obvious...  
> **username_6**: Sure any $K_4$ minor works, assuming you mean the obvious generalization.  
> **username_7**: @Walter: Now that the problem has been solved, could you perhaps write a short answer and accept it?  
> **username_0**: @Jukka: Should I write an answer to my own question? Maybe @Tsuyoshi could transform his comment in a lapidary answer to this ah-so-dumb question, and I'll accept it.  
> **username_8**: @Peter of course it's always possible to make any face of a planar graph the outer face and convex  
> **username_5**: @Suresh: I agree. But if you want to solve the convex hull question completely, you have to show you can make any subset of a face of a planar graph the convex hull. I think you should be able to do this as well, but couldn't come up with a proof in the few minutes I was thinking about it.  
> **username_0**: @Jukka: Let me clarify that I've nothing against answering my own question. It just seems curious (especially if the answer came from another person).  
> **username_1**: As far as I am concerned, it is fine for you to post an answer.  I only happened to post the comment first.  

---

## 1 answers

### Answer by username_0 on 2011-03-04. Score: 6 | Accepted answer

This question turned out to be trivial. As username_6 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 username_1 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 username_5indicated, 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).

> **Comments:**
> **username_8**: you should accept this answer so the question doesn't keep popping up every month or so  
> **username_0**: @Suresh: I've tried to accept it, but the system said: "You can accept your own answer in 2 days".  
> **username_5**: I think that as long as the answer has positive votes, the question won't keep popping up.  

---

