I've seen a bunch of similar MO questions, yet hopefully this is not a complete duplicate.
Consider $n$ halfplanes in $\mathbb{R}^2$ with their borders in general position, that is, no point of $\mathbb{R}^2$ lies on three or more lines, and no two lines are parallel. The plane will then be separated into $m = {n + 1 \choose 2} + 1$ regions. We can now associate a bipartite graph $G \leq K_{n, m}$ with this arrangement so that vertices of the left half correspond to halfplanes, vertices of the right half correspond to regions, and $xy \in E(G)$ iff the halfplane $x$ contains the region $y$.
Here are my questions:
- How many non-isomorphic graphs $G$ arise from all possible arrangments of $n$ halfplanes (at least asymptotically)? If we denote this quantity as $I(n)$, then one can easily see $I(1) = I(2) = 1$, and $I(3) = 4$. To see the last identity, consider the triangle $T$ formed by the three lines; isomorphism of arising graphs depends only on the number of halfplanes containing $T$ (there could be $0$, $1$, $2$, or $3$).
- Given a graph $G$, how hard is it to recognize it as corresponding to a halfplane arrangement (and, possibly, reconstruct an arrangement giving rise to $G$)?
Clarification: to avoid nasty side-effects, we consider the $(n, m)$-partition of the graph vertices to be fixed (that is, in Q1 only isomorphisms respecting the partition are considered, and in Q2 the partition is known in addition to the graph).
