Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This question is related to the question of drawing a combinatorial 3-configuration of points and lines with straight lines. We only relax the condition and admit drawings with pseudolines. Let us call a combinatorial configuration that can be drawn with pseudolines topologically realizable. 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.

It is known that neither the Fano plane (73) nor the Moebius-Kantor configuration (83) are topologically realizable. Among the ten (103) combinatorial configurations nine are (geometrically) realizable and one is only topologically 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 topologically realizable?

The book "Configurations of Points and Lines" by Branko Grunbaum discusses this problem as a classification problem but not as a complexity problem.

share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.