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.
No comments:
Post a Comment