Let $\mathcal{ D}=\{ D_0,\ldots,D_{ n-1}\}$ be a set of $n$ topological disks in the plane and let $\mathcal{ A} := \mathcal{ A}(\mathcal{ D})$ be the arrangement induced by $\mathcal{ D}$. For two disks $D_i,D_j\in\mathcal{ D}$, let $\Delta_{ ij}$ be the number of connected components of $D_i\cap D_j$, and let $\Delta := \max_{ i,j} \Delta_{ ij}$. We show that the diameter of $\mathcal{ G}^*$, the dual graph of $\mathcal{ A}$, can be bounded as a function of $n$ and $\Delta$. Thus, any two points in the plane can be connected by a Jordan curve that crosses the disk boundaries a number of times bounded by a function of $n$ and $\Delta$. In particular, for the case of two disks, we prove that the diameter of $\mathcal{ G}^*$ is at most $\max\{ 2,2\Delta\}$ and this bound is tight. For the general case of $n>2$ disks, we show that the diameter of $\mathcal{ G}^*$ is $O(n^3 2^n \Delta)$. We achieve this by proving that the number of maximal faces in $\mathcal{ A}$ -- faces whose ply is more than the ply of their neighboring faces -- is $O(n^2 2^n \Delta)$. To this end, we first show that the number of maximum faces -- faces whose ply is $n$ -- is $O(n^2\Delta)$; the latter bound, which is of independent interest, is tight in the worst case.
Categories: math.CO cs.CG