Thickness of Sphere-of-Influence Graphs (2007)

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 rx be the minimum distance from x to S-x, and let Bx denote the open ball of radius rx with center x. The sphere-of-influence graph (SIG) generated by S, denoted GS, is the intersection graph of {Bx: x ∈ S}; equivalently, x and y are adjacent in GS if and only if the Euclidean distance d(x,y) is less than rx+ry.

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; K8 is, but K12 is not (Kézdy-Kubicki [KK]). Note that K8 has thickness 2, but K9, K10, and K11 have thickness 3.
3) SIGs may have induced subgraphs that are not SIGs. For example, a claw (K1,3) is not a SIG, but the graph obtained by appending one edge at a leaf is a SIG.

Similar questions can be asked about "closed sphere-of-influence graphs", where x and y are adjacent if d(x,y)≤rx+ry.

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