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 survey 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.
