Show that there can be an exponential number of maximal cliques in a disk intersection graph

21 Views Asked by At

This is Exercise 14 of "Efficient graph representations" (Spinrad), Chapter 3:

Show that there can be exponentially many maximal cliques in a disk intersection graph.

The "canonical" example (as noted in this paper, Theorem 1, and also this paper, page 264) is to place $2n$ points evenly on a circle of radius, say, $1+\varepsilon$ for very small $\varepsilon>0$, then take unit disks centered at each of the $2n$ points. If $\varepsilon$ is small enough, we attain a complete $n$-partite graph with $2^n$ maximal cliques.

This is represented as a disk graph and a straight-line graph in the 2nd source:

enter image description here

My question is: Are there any other examples of disk graphs with exponentially many maximal cliques? (By "other examples" I mean substantively different; not just a small perturbation of the points-on-a-circle example)