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 email@example.com and to firstname.lastname@example.org