Note on the number of edges in families with linear union-complexity

Abstract

We give a simple argument showing that the number of edges in the intersection graph $G$ of a family of $n$ sets in the plane with a linear union-complexity is $O(\omega (G)n)$. In particular, we prove $\chi (G)\le \text{col}(G)<19\omega (G)$ for intersection graph $G$ of a family of pseudo-discs, which improves a previous bound.

background and related work is now more complete; presentation improved

References in corpus (1)

• Triangle-free geometric intersection graphs with large chromatic number