Representing Graphs by Spheres in 3-Space



Every planar graph can be realized in the plane by a packing of incongruent disks for the vertices such that two disks touch each other if and only if the corresponding vertices are adjacent.

Question: Which graphs can be realized in R^3 in a corresponding way by incongruent spheres?

The structure of these graphs is interesting. Neil Sloan says that K_6 is not in this class, but K_5 is.

Question: Does there exist a ``Kuratowski type'' forbidden subgraph characterization of graphs with incongruent spherical representations?

Paul Seymour asks if two linked triangles can be so represented.

[Note added by Dan Archdeacon: The higher dimensional analogues naturally suggest themselves. In particular, given a graph G, what is the minimum n such that G can be represented in R^n by (n-1)-spheres? Is there a constant c such that every graph is representable in R^c by (c-1)-spheres?]


Submitted by: Heiko Harborth, Diskrete Mathematik, Technische Universiat Braunschweig, Pockelsstrasse 14, D-38106 Braunschweig, Germany

Send comments to dan.archdeacon@uvm.edu and to h.harborth@tu-bs.de

August, 1995