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