Return to Question

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

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.

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

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.

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

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.

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

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.