12
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ Gr\"{u}nbaum's book definitely does not give an answer. $\endgroup$
    – Leah Wrenn Berman
    Mar 12, 2010 at 3:01

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Would Mnev's Universality Theorem address the realizability question with straight lines? My (basically nonexistent) understanding was that it would/could apply via oriented matroids, and thus would have something to say about realizations by pseudolines. (I guess you could then ask if the pseudoline configuration was stretchable, but that's hard too...) $\endgroup$
    – Leah Wrenn Berman
    Mar 20, 2010 at 18:10
2
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thank for your effort. I am not really familiar with Mnev's universality theorem and am not sure what are the implications of your answers to the complexity issue of the realizability question. I will try to ask a related question that may shed some additional light to the problem. $\endgroup$
    – Tomaž Pisanski
    Mar 19, 2010 at 14:37
  • $\begingroup$ @Peter: Do you know if Mnev's universality theorem can distinguish between lines and pseudolines? See my related question: mathoverflow.net/questions/18758/… $\endgroup$
    – Tomaž Pisanski
    Mar 21, 2010 at 10:01
  • $\begingroup$ A pseudoline arrangement can be thought of (intuitively) as a set of curves in the projective plane which "look like" lines; i.e., any pair cross exactly once. The realizability space of a pseudoline arrangement is the set of straight line arrangements realizing it. What Mnev showed was that, for any semialgebraic variety (set of equations and inequalities over R), there is a pseudoline arrangement with essentially the same realization space. I showed that this construction is in P, implying stretchability of pseudolines is equivalent to the existential theory of the reals. $\endgroup$
    – Peter Shor
    Mar 22, 2010 at 17:11
  • $\begingroup$ Thus (to continue the discussion in another comment), Mnev's universality theorem is about the difference between lines and pseudolines. A good reference on it is "The universality theorem for oriented matroids and polytopes," by Richter-Gebert. $\endgroup$
    – Peter Shor
    Mar 22, 2010 at 17:21
  • $\begingroup$ Another good reference is Peter's own paper, "Stretchability of Pseudolines is NP-Hard," which includes a description of Mnev's proof. It's in Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift (which is accessible via Google Books). $\endgroup$
    – Joseph O'Rourke
    Jun 3, 2010 at 2:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.