Crossing number of some Sphere of Influence Graphs and relation to their coloring number

Question

My motivation is to apply some graph theoretic methods in real analysis (like in a simple proof that every open real set $ A $ is coutable union of disjoint graph - take the connected component of the intersection graph of $ A = \bigcup_\alpha I_\alpha$: $G=(A,E) $ where $ xEy $ iff there exists an interval $ I_\alpha $ such that $ x,y \in I $. More proofs can be found in 1):

Below is a statement of Berkuwich covering theorem (A statement of [2] with few minor changes):

Let $ N $ be a positive integer. There is a constant $ K = K(2) $ with the following property. Let $ B = \{ B_\alpha \}_\alpha$ be any collection of balls in $ \mathbb{R}^2 $ with the property that the interior of no ball contains the center of any other. Then we may write $ B = \mathcal{B}_1 \cup \ldots \cup \mathcal{B}_k $ so that each $ \mathcal{B}_j $ $ j = 1,\ldots,K $ is a collection of balls with pairwise disjoint closures.

Here by a ball we mean a set $ B $ satisfying $ \mathbb{B(x,r)} \subseteq B \subseteq \overline{\mathbb{B}}(x,r) $ for some $ x \in \mathbb{R^2} $ and some $ r> 0 $.

Than apply that idea we can define the Sphere of Influence Graph of the collection to be the graph $ G = (B,E) $ such that two intersect balls connected by an edge.

This idea discussed in [3][4].

This SIG graph has also the property that the interior of no ball contains the center of the other.

In that setting we need to find the chromatic number of the SIG of $ B $.

Firstly, this leads to an (known) obseration that we need only find a bound for finite $ B $ (using De Bruijn–Erdős theorem). So we can assume that B is finite.

Than, one can conjeture that under the constain we get a planar graph, sadly it's not the case, but we may consider their cross-number.

However, even if we have their cross-number what can we get about their chromatic number?

So there are two questions:

1. What is the cross-number of the SIG of $ B $ under the constrain that the interior of no ball contains the center of any other. A good approximation is useful too.
2. Even we find the cross-number, what can we deduce about their chromatic number? Maybe it's possible to apply some computational methods (like in the four-color theorem proof). A good approximation is useful too.

I know that this strateghy isn't the best one to find the Berkuwich number (works only at the plane), but I find it interesting because of the graph-theoretic asspects. Thanks.

Remark:

The question arises an Eudclid-geometry question: Is there exists a constant $ k $ such that if we take any collection $ \{ C_i \}_{i=1}^k $ of closed ball that the interior of no ball contains the center of any other, and than draw a segment between centers of intersected circle, than the maximal number of segment intersections is at most $ k $? What is the value of that number?

1 Orest Xherija (https://math.stackexchange.com/users/56880/orest-xherija), Any open subset of $\Bbb R$ is a at most countable union of disjoint open intervals. [Collecting Proofs], URL (version: 2015-04-18): https://math.stackexchange.com/q/318299.

[2] Krantz, Steven G., and Harold R. Parks. Geometric integration theory. Springer Science & Business Media, 2008.‏

[3] Soss, Michael A. "On the size of the euclidean sphere of influence graph." CCG. 1999.‏

[4] Erdös, Paul, et al. "Intersection graphs for families of balls in RN." European Journal of Combinatorics 9.5 (1988): 501-505.‏

Answer 1

In a Euclidean space of any dimension, for a system of balls no center of which is interior to another ball, each ball can only be touched by $O(1)$ larger balls. This is a special case of Lemma 3.6 of Shang-Hua Teng's dissertation Points, Spheres, and Separators: A Unified Geometric Approach to Graph Partitioning (CMU, 1991), proven by combining the observation that the number of balls containing any point is at most the kissing number (Lemma 3.2) and that the larger balls that touch a given ball cover at least the same area as the given ball within a 3x expansion of the given ball. In the plane, for instance, the kissing number is 6 and the 3x expansion gives another factor of 9, so each ball can be touched by at most 54 larger balls. I think this bound is not very tight, but it immediately implies that the chromatic number of the intersection graph of the balls is at most 55 (just color the balls greedily from largest to smallest).

By the same argument there are at most $54n$ edges and therefore at most $\tbinom{54n}{2}=O(n^2)$ crossings.

However, the crossing number can be quadratic. Consider two equal-sized balls $B_1$ and $B_2$, just barely touching each other, and a third ball $B_3$ that avoids the centers of $B_2$ but crosses the boundary of their union four times. Then $B_3$ can be arbitrarily larger than $B_1$ and $B_2$, and there is a small arc of $B_3$'s boundary between $B_1$ and $B_2$ where this construction can be repeated with another pair $B'_1$ and $B'_2$, etc. Repeating this construction $n$ times produces $n$ triangles from $2n+1$ balls, with each of the $\tbinom{n}{2}$ pairs of triangles forming two crossings.

Answer 2

I believe that it's not the direction after all. If we look at the geometric question than we get the there exists no such k (the proof is very trivial, take unbounded connected components of 4 intersection circles).

So the question is totally trivial, and you can put it as "closed".