most recent 30 from http://mathoverflow.net 2013-05-25T20:11:32Z http://mathoverflow.net/feeds/question/18758 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/18758/drawing-a-combinatorial-3-configuration-of-points-and-lines-with-pseudolines Tomaž Pisanski 2010-03-19T15:14:02Z 2010-07-07T02:07:45Z

<p>This question is related to the question of drawing a <a href="http://mathoverflow.net/questions/17635/drawing-3-configurations-of-points-and-lines-with-straight-lines" rel="nofollow">combinatorial 3-configuration of points and lines with straight lines</a>. We only relax the condition and admit drawings with pseudolines. Let us call a combinatorial configuration that can be drawn with pseudolines <strong>topologically realizable</strong>. This notion is readily carried over to the corresponding Levi graph of the configuration. Namely, the graph is topologically realizable if it is the Levi graph (=incidence graph) of a configuration of points and pseudolines.</p> <p>It is known that neither the Fano plane (7₃) nor the Moebius-Kantor configuration (8₃) are topologically realizable. Among the ten (10₃) combinatorial configurations nine are (geometrically) realizable and one is only topologically realizable. </p> <p>I would like to know what is known about the status of the following complexity decision problem.</p> <blockquote> <p><strong>Input:</strong> Cubic connected bipartite graph G of girth at least 6.</p> <p><strong>Question:</strong> Is G topologically realizable? </p> </blockquote> <p>The book "Configurations of Points and Lines" by Branko Grunbaum discusses this problem as a classification problem but not as a complexity problem.</p>