Drawing 3-configurations of points and lines with straight lines It is well-known that the black-and-white coloring of the Heawood graph on 14 vertices determines a combinatorial 3-configuration with 7 "points" and 7 "lines", known as Fano plane. Similarly, any cubic bipartite graph of girth at least 6 with a given black-and-white coloring can be regarded as the Levi graph or incidence graph of a 3-configuration.  The Fano plane can be drawn in the Euclidean plane with 6 straight lines and one curved line but not with all lines straight. There are many combinatorial 3-configurations, such as Pappus or Desargues configurations that can be realized as geometric configurations of points and lines in the Euclidean plane. Call such configuration realizable. It is easy to see that if a combinatorial configuration is realizable then its dual configuration is realizable. (The combinatorial dual is obtained by interchanging black and white colors in the coloring of its Levi graph). This means that the property of realizability is, in fact, a property of bipartite graphs and the Heawood graph is not realizable.
I would like to know what is known about the status of the following complexity decision problem.

Input: Cubic connected bipartite graph G of girth at least 6.
Question: Is G realizable?

I am aware of recent book "Configurations of Points and Lines" by Branko Grunbaum, the book by
Juergen Bokowski: "Computational Oriented Matroids" and the book "Computational Synthetic Geometry" by
Bokowski and Sturmfels. I am not sure if any of them gives the final answer to this problem.
 A: Ten minutes ago I gave the wrong answer. I said:
"You haven't mentioned Mnev's universality theorem, so I'll assume you don't know about it. Bokowski and Sturmfels is too old to refer to it, and for some reason the other two don't seem to mention it, at least not as far as I can tell by looking at their contents and indexes online. One of the consequences of Mnev's universality theorem is that the realizability question above is equivalent to the existential theory of the reals. You can learn about it from a wikipedia article, and a very nice article by Richter-Gebert available online."
Oops. I just realized this isn't right ... From the graph viewpoint, I think you just care whether a line passes through a point, and not whether it goes to the left or right. You should still look at Mnev's universality theorem, but that doesn't immediately give the answer to the question. Let me think about it.
A: Let's try this again. If there weren't a degree constraint on the graph, then you could adapt the proof of Mnev's universality theorem (see my previous answer) to show that the problem was equivalent to the existential theory of the reals. So one approach to try is to find gadgets to reduce arbitrary degree to degree three (like SAT → 3-SAT). I'm almost positive you can do this for some constant degree. I'm not at all sure whether you can get it down to degree 3, though. 
