<p>Schramm proved that every planar graph is the contact graph of some set of smooth convex objects in the plane in <a href="http://arxiv.org/abs/0709.0710" rel="nofollow">his PhD thesis (Princeton, 1990)</a> using Brouwer's Fixed Point Theorem.</p>

<p>A nice survey of this and other results related to Koebe's Theorem is in <a href="http://linkinghub.elsevier.com/retrieve/pii/0012365X93E0068F" rel="nofollow">a survey by Sachs</a>.</p>

CC BY-SA 3.0
2011-04-14T15:17:01.610Z
2011-04-15T08:00:47.787Z
2011-04-15T08:00:47.787Z
RJK
<p>If you use triangles, it can be done.  Perhaps not easier than Koebe though...</p>

<p><a href="http://journals.cambridge.org/article_S0963548300001139" rel="nofollow">de Fraisseix, Ossona de Mendez and Rosenstiehl. On Triangle Contact Graphs. CPC 3(2): 233-246, 1994.</a></p>

CC BY-SA 3.0
2011-04-15T14:34:36.760Z
I don't think that the triangles in that paper are fat but the proof is easy, based on a representation with T-shapes that follows from st orderings.
domotorp
CC BY-SA 3.0
2011-04-14T15:04:06.883Z
2011-04-14T15:04:06.883Z
RJK
<p>One thing we do know is that you can't recreate Koebe's theorem with rectangles. Contact graphs of rectangles can't capture $K_4$. </p>

CC BY-SA 3.0
2011-04-14T04:22:56.570Z
Axis parallel rectangles? Or any rectangles?
Sariel Har-Peled
CC BY-SA 3.0
2011-04-14T04:24:27.740Z
axis parallel rectangles.
Suresh Venkat
CC BY-SA 3.0
2011-04-14T04:00:32.147Z
2011-04-14T04:00:32.147Z
Suresh Venkat
<p>There's a <a href="http://arxiv.org/abs/1104.1482" rel="nofollow">new paper on the arxiv</a> by Duncan, Gansner, Hu, Kaufman and Kobourov on contact graph representations. They show that 6 sided polygons are necessary and sufficient. The hexagons can be convex, but it wasn't clear to me on a first reading whether they were fat as well. </p>

CC BY-SA 3.0
2011-04-17T06:23:49.687Z
Yo yo. I just discovered this paper myself... They are using the de Fraisseix etal result mentioned above, and a result by Kant...
Sariel Har-Peled
CC BY-SA 3.0
2011-04-17T09:45:43.380Z
Here "contact" is defined differently. Point contact is disallowed, from my reading.
RJK
CC BY-SA 3.0
2011-04-17T17:27:18.500Z
I imagine that's reasonable for polygonal representations (since any non-vertex contact will necessarily be non-point) ?
Suresh Venkat
CC BY-SA 3.0
2011-04-18T03:03:44.297Z
Since here there are only three allowable slops, the touch must be via parallel edges touching each other... No?
Sariel Har-Peled
CC BY-SA 3.0
2011-04-17T05:39:19.663Z
2011-04-17T05:39:19.663Z
Suresh Venkat
<p>Gerd Wegner in <em>his</em> PhD thesis (Georg-August-Universität, Göttingen, 1967) proved that any graph is the contact graph of a set of three-dimensional convex polytopes (but he credits the first unpublished proof of the result to Grünbaum).  This is a short proof.</p>

CC BY-SA 3.0
2011-04-15T13:23:59.553Z
There are easy direct proofs of that, for example by putting points on the moment curve and computing their Voronoi diagram. Here the fatness condition however fail miserably...
Sariel Har-Peled
CC BY-SA 3.0
2011-04-15T15:04:54.807Z
Ah, I completely misunderstood "fat".  I'm embarrassed to admit (but I guess it must be clear now) that I didn't know the definition, until I googled "fat triangle".  Could you please provide a reference/definition for this concept?
RJK
CC BY-SA 3.0
2011-04-17T04:02:14.750Z
Also, the representation I mention can be used to represent any graph in this way - not only planar graphs.
Sariel Har-Peled
CC BY-SA 3.0
2011-04-17T09:44:24.657Z
Thanks for the clarification of "fat" in the question.  It's worth pointing out that I did not mention planar either in this post.  For a given value of fatness, each graph is representable by fat convex polytopes in some (high enough) dimension.  The obvious question is whether the bound on dimension can be uniform over all graphs. Has this been studied?
RJK
CC BY-SA 3.0
2011-04-18T03:01:58.917Z
Not as far as I know, but I am not very knowledgable about such stuff...
Sariel Har-Peled
CC BY-SA 3.0
2011-04-15T07:59:00.253Z
2011-04-15T07:59:00.253Z
RJK
<p>You didn't say the fat objects had to be two-dimensional, did you? <a href="http://www.math.tu-berlin.de/~felsner/Paper/cubes.pdf" rel="nofollow">Felsner and Francis prove that it's always possible with axis-parallel cubes in 3d</a>. But, the proof involves Schramm's generalizations of Koebe-Thurston-Andreev, so it's not exactly a simpler result. They also mention along the way that for four-connected maximal planar graphs it's possible to use parallel-sided equilateral triangles.</p>

CC BY-SA 3.0
2011-04-14T09:54:36.293Z
Well, that's a nice question too, I guess.  Is there a quick proof that every planar graph is representable as the contact graph of spheres?
RJK
CC BY-SA 3.0
2011-04-14T05:52:55.393Z
2011-04-14T05:52:55.393Z
David Eppstein
<p>There is a beautiful theorem of Koebe (see <a href="http://en.wikipedia.org/wiki/Circle_packing_theorem" rel="nofollow" rel="nofollow">here</a>) that states that any planar graph can be drawn as kissing graph of disks (very romantic...). (Putting it somewhat differently, any planar graph can be drawn as the intersection graph of disks.) </p>

<p>Koebe theorem is not very easy to prove. My question: Is there an easier version of this theorem where instead of disks one is allowed to use any fat convex shapes (convexity might be open to negotiations, but not fatness). Note, that every vertex can be a different shape.</p>

<p>Thanks...</p>

<p>Clarification: For a shape $X$, let $R(X)$ be the radius of the smallest enclosing ball of $X$, and let $r(X)$ let me the radius of the largest enclosed ball in $S$. The shape $S$ is <em>$\alpha$-fat</em> if $R(x) /r(x) \leq \alpha$. (This is not the only definition for fatness, BTW.)</p>

CC BY-SA 3.0
2011-04-14T03:59:33.380Z
to be slightly pedantic: Koebe's theorem is about contact graphs, which are slightly different to intersection graphs. Which version would you prefer ?
Suresh Venkat
CC BY-SA 3.0
2011-04-14T09:59:28.913Z
So I assume fatness is required due to the fact that every planar graph is the intersection graph of segments in the plane (Chalopin & Gonçalves, STOC 09).  If they aren't fat, then kissing is the same as intersection.  (Hm, the last sentence is strange taken out of context!)
RJK
CC BY-SA 3.0
2011-04-14T13:42:32.537Z
Fatness just make life easier as far as doing other things with the graph (for example, finding a separator).
Sariel Har-Peled
CC BY-SA 3.0
2011-04-14T15:10:47.687Z
I wonder if the real question here is: "give a simple proof of Koebe's theorem" rather than "find low-complexity fat shape families that simulate Koebe's theorem"
Suresh Venkat
CC BY-SA 3.0
2011-04-15T01:03:24.177Z
Sure. Thats a valid interpretation. However, I think to get a simple proof of Koebe theorem, one needs to relax it somehow...
Sariel Har-Peled
<cg.comp-geom><planar-graphs>
Planar graph via the intersection of fat thingies?
Sariel Har-Peled
# Planar graph via the intersection of fat thingies?

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

There is a beautiful theorem of Koebe (see [here](http://en.wikipedia.org/wiki/Circle_packing_theorem)) that states that any planar graph can be drawn as kissing graph of disks (very romantic...). (Putting it somewhat differently, any planar graph can be drawn as the intersection graph of disks.)

Koebe theorem is not very easy to prove. My question: Is there an easier version of this theorem where instead of disks one is allowed to use any fat convex shapes (convexity might be open to negotiations, but not fatness). Note, that every vertex can be a different shape.

Thanks...

Clarification: For a shape $X$, let $R(X)$ be the radius of the smallest enclosing ball of $X$, and let $r(X)$ let me the radius of the largest enclosed ball in $S$. The shape $S$ is *$\alpha$-fat* if $R(x) /r(x) \leq \alpha$. (This is not the only definition for fatness, BTW.)

**Tags:** cg.comp-geom, planar-graphs

> **Comments:**
> **username_1**: to be slightly pedantic: Koebe's theorem is about contact graphs, which are slightly different to intersection graphs. Which version would you prefer ?  
> **username_2**: So I assume fatness is required due to the fact that every planar graph is the intersection graph of segments in the plane (Chalopin & Gonçalves, STOC 09).  If they aren't fat, then kissing is the same as intersection.  (Hm, the last sentence is strange taken out of context!)  
> **username_0**: Fatness just make life easier as far as doing other things with the graph (for example, finding a separator).  
> **username_1**: I wonder if the real question here is: "give a simple proof of Koebe's theorem" rather than "find low-complexity fat shape families that simulate Koebe's theorem"  
> **username_0**: Sure. Thats a valid interpretation. However, I think to get a simple proof of Koebe theorem, one needs to relax it somehow...  

---

## 6 answers

### Answer by username_4 on 2011-04-14. Score: 10 | Accepted answer

You didn't say the fat objects had to be two-dimensional, did you? [Felsner and Francis prove that it's always possible with axis-parallel cubes in 3d](http://www.math.tu-berlin.de/~felsner/Paper/cubes.pdf). But, the proof involves Schramm's generalizations of Koebe-Thurston-Andreev, so it's not exactly a simpler result. They also mention along the way that for four-connected maximal planar graphs it's possible to use parallel-sided equilateral triangles.

> **Comments:**
> **username_2**: Well, that's a nice question too, I guess.  Is there a quick proof that every planar graph is representable as the contact graph of spheres?  

---

### Answer by username_2 on 2011-04-14. Score: 7

Schramm proved that every planar graph is the contact graph of some set of smooth convex objects in the plane in [his PhD thesis (Princeton, 1990)](http://arxiv.org/abs/0709.0710) using Brouwer's Fixed Point Theorem.

A nice survey of this and other results related to Koebe's Theorem is in [a survey by Sachs](http://linkinghub.elsevier.com/retrieve/pii/0012365X93E0068F).


---

### Answer by username_2 on 2011-04-14. Score: 7

If you use triangles, it can be done. Perhaps not easier than Koebe though...

[de Fraisseix, Ossona de Mendez and Rosenstiehl. On Triangle Contact Graphs. CPC 3(2): 233-246, 1994.](http://journals.cambridge.org/article_S0963548300001139)

> **Comments:**
> **username_3**: I don't think that the triangles in that paper are fat but the proof is easy, based on a representation with T-shapes that follows from st orderings.  

---

### Answer by username_1 on 2011-04-14. Score: 6

One thing we do know is that you can't recreate Koebe's theorem with rectangles. Contact graphs of rectangles can't capture $K\_4$.

> **Comments:**
> **username_0**: Axis parallel rectangles? Or any rectangles?  
> **username_1**: axis parallel rectangles.  

---

### Answer by username_1 on 2011-04-17. Score: 4

There's a [new paper on the arxiv](http://arxiv.org/abs/1104.1482) by Duncan, Gansner, Hu, Kaufman and Kobourov on contact graph representations. They show that 6 sided polygons are necessary and sufficient. The hexagons can be convex, but it wasn't clear to me on a first reading whether they were fat as well.

> **Comments:**
> **username_0**: Yo yo. I just discovered this paper myself... They are using the de Fraisseix etal result mentioned above, and a result by Kant...  
> **username_2**: Here "contact" is defined differently. Point contact is disallowed, from my reading.  
> **username_1**: I imagine that's reasonable for polygonal representations (since any non-vertex contact will necessarily be non-point) ?  
> **username_0**: Since here there are only three allowable slops, the touch must be via parallel edges touching each other... No?  

---

### Answer by username_2 on 2011-04-15. Score: 0

Gerd Wegner in *his* PhD thesis (Georg-August-Universität, Göttingen, 1967) proved that any graph is the contact graph of a set of three-dimensional convex polytopes (but he credits the first unpublished proof of the result to Grünbaum). This is a short proof.

> **Comments:**
> **username_0**: There are easy direct proofs of that, for example by putting points on the moment curve and computing their Voronoi diagram. Here the fatness condition however fail miserably...  
> **username_2**: Ah, I completely misunderstood "fat".  I'm embarrassed to admit (but I guess it must be clear now) that I didn't know the definition, until I googled "fat triangle".  Could you please provide a reference/definition for this concept?  
> **username_0**: Also, the representation I mention can be used to represent any graph in this way - not only planar graphs.  
> **username_2**: Thanks for the clarification of "fat" in the question.  It's worth pointing out that I did not mention planar either in this post.  For a given value of fatness, each graph is representable by fat convex polytopes in some (high enough) dimension.  The obvious question is whether the bound on dimension can be uniform over all graphs. Has this been studied?  
> **username_0**: Not as far as I know, but I am not very knowledgable about such stuff...  

---

