14
$\begingroup$

There is a beautiful theorem of Koebe (see here) 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.)

$\endgroup$
5
  • $\begingroup$ to be slightly pedantic: Koebe's theorem is about contact graphs, which are slightly different to intersection graphs. Which version would you prefer ? $\endgroup$ Apr 14, 2011 at 3:59
  • $\begingroup$ 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!) $\endgroup$
    – RJK
    Apr 14, 2011 at 9:59
  • $\begingroup$ Fatness just make life easier as far as doing other things with the graph (for example, finding a separator). $\endgroup$ Apr 14, 2011 at 13:42
  • 3
    $\begingroup$ 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" $\endgroup$ Apr 14, 2011 at 15:10
  • 2
    $\begingroup$ Sure. Thats a valid interpretation. However, I think to get a simple proof of Koebe theorem, one needs to relax it somehow... $\endgroup$ Apr 15, 2011 at 1:03

6 Answers 6

10
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – RJK
    Apr 14, 2011 at 9:54
7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – domotorp
    Apr 15, 2011 at 14:34
7
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Axis parallel rectangles? Or any rectangles? $\endgroup$ Apr 14, 2011 at 4:22
  • $\begingroup$ axis parallel rectangles. $\endgroup$ Apr 14, 2011 at 4:24
4
$\begingroup$

There's a new paper on the arxiv 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.

$\endgroup$
4
  • $\begingroup$ Yo yo. I just discovered this paper myself... They are using the de Fraisseix etal result mentioned above, and a result by Kant... $\endgroup$ Apr 17, 2011 at 6:23
  • $\begingroup$ Here "contact" is defined differently. Point contact is disallowed, from my reading. $\endgroup$
    – RJK
    Apr 17, 2011 at 9:45
  • $\begingroup$ I imagine that's reasonable for polygonal representations (since any non-vertex contact will necessarily be non-point) ? $\endgroup$ Apr 17, 2011 at 17:27
  • $\begingroup$ Since here there are only three allowable slops, the touch must be via parallel edges touching each other... No? $\endgroup$ Apr 18, 2011 at 3:03
0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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... $\endgroup$ Apr 15, 2011 at 13:23
  • $\begingroup$ 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? $\endgroup$
    – RJK
    Apr 15, 2011 at 15:04
  • $\begingroup$ Also, the representation I mention can be used to represent any graph in this way - not only planar graphs. $\endgroup$ Apr 17, 2011 at 4:02
  • $\begingroup$ 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? $\endgroup$
    – RJK
    Apr 17, 2011 at 9:44
  • $\begingroup$ Not as far as I know, but I am not very knowledgable about such stuff... $\endgroup$ Apr 18, 2011 at 3:01

Your Answer

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

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