Originator: Felix Lazebnik (presented by Sebastian Cioba - REGS 2011)
Definitions/Background: Lines are in general position in the plane if(no three lines are concurrent and no two lines are parallel. Any $n$ such lines divide the plane into ${n+1\choose 2}+1$ regions. Given a set $A$ of $n$ lines in the plane in general position, define the graph $G(A)$ as follows: its vertices are the ${n+1\choose 2}+1$ regions into which the lines of $A$ divide the plane, and two vertices are adjacent if the corresponding regions share a common segment. The graph $G(A)$ is planar and bipartite; it is in a sense the "dual" of the line arrangement.
Problem 1: Characterize the graphs $G(A)$.
Comments: The bounded faces of $G(A)$ are $4$-cycles, and the outer boundary has length $2n$. Furthermore, opposite edges of the outer boundary are joined by "face-paths" consisting of $n-1$ faces; each such face-path corresponds to a line in $A$, traversing its intersections with other lines. Unfortunately, these necessary conditions do not suffice to characterize the graphs in this family. The paths generated in this way form a "pseudoline arrangement"; in general, the problem of which pseudoline arrangements can be "straightened" (arising from lines) is a well-known problem addressed by oriented matroids. Perhaps this special case is simpler.
Problem 2: Find lower and upper bounds on the number of isomorphism classes of graphs of the form $G(A)$ such that $|A|=n$.
Comments:
There is only one class for $n\le4$, but this is not true for $n\geq 5$.