**Originators: ** B. Allgeier & G. Kubicki
(presented by Ben Allgeier- REGS 2007)

**Definitions: **Let *S* be a set of *n* points
in the plane. For *x ∈ S*, let *r _{x}* be the
minimum distance from

The *planar thickness* (or simply *thickness*) of a graph
*G* is the minimum number of planar graphs whose union is *G*.

**Conjecture:** The thickness of SIGs is bounded, perhaps by 6
or less.

**Comments:** No SIG is known with thickness more than 2.

1) Bateman and Erdős [BE] showed that an *n*-vertex SIG has at
most *18n* edges. This follows from their study of intersection
properties of circles in the plane. Touissant conjectured that *9n* may
be an upper bound.

2) It is not known which complete graphs are SIGs; *K _{8}*
is, but

3) SIGs may have induced subgraphs that are not SIGs. For example, a claw (

Similar questions can be asked about "closed sphere-of-influence graphs", where
*x* and *y* are adjacent if
*d(x,y)≤r _{x}+r_{y}.*

**References:**

[BE] Bateman, Paul; Erdős, Paul. Geometrical extrema suggested by a
lemma of Besicovitch. Amer. Math. Monthly 58, (1951). 306--314.

[KK] Kézdy, A. E.; Kubicki, G. *K _{12}* is not a closed
sphere-of-influence graph. Intuitive geometry (Budapest, 1995), 383--397,
Bolyai Soc. Math. Stud., 6, János Bolyai Math. Soc., Budapest, 1997.