This question is related to this previous question. Many combinatorial configurations have Levi graphs which may be represented as derived graphs obtained from voltage graphs over a cyclic group; in a number of such cases, it is possible to represent the combinatorial configuration as a geometric configuration (i.e., using points and straight lines in the Euclidean plane).

Given a bipartite graph which is obtained from a voltage graph, we can view it as a Levi graph of some combinatorial configuration. Is it possible to draw all such configurations using pseudolines? If not, are there easy/known constraints on the ones that fail? (e.g., if there are more than x points in the configuration, then things work? You can't use such-and-so groups as the cyclic group for the voltage graph?)

(Does the Heawood graph have a voltage-graph representation? If so, it makes the first question easy to answer, but the second one is still interesting. Maybe.)

  • $\begingroup$ It might help if you define voltage graphs or link to a definition of them. (It might not, though, because perhaps anybody who can answer this question already knows what a voltage graph is.) $\endgroup$ – Michael Lugo Mar 20 '10 at 0:41
  • $\begingroup$ @Michael: "Voltage graph" is a combinatorial tool composed of the base graph and the assignment of group elements to arcs in such a way that the opposing arcs of an edge are assigned inverse group elements. It completely describes the covering graph together with the regular covering projection. The term is explained and used a lot in the book "Topological Graph Theory" by Gross and Tucker. $\endgroup$ – Tomaž Pisanski Mar 20 '10 at 9:42

The fist part of your question has a negative answer, since both Fano plane (73) and Moebius-Kantor configuration (83) are cyclic configurations. Here it is shown that the cyclic covering graphs over a dipole with girth at least 6 are exactly Levi graphs of combinatorial cyclic configurations. In your terminology, each Levi graph of a cyclic configuration has a "voltage-graph representation". Note: a dipole is a graph consisting of two vertices and a number of parallel edges between them. In particular both the Heawood graph and the Moebius-Kantor graph are counterexaples.

If v = uw is a composite number, it is sometimes possible to find a suitable voltage graph on 2u vertices and voltages from the cyclic group Zw to produce a straight-line drawing of the corresponding polycyclic configuration (v3). Unfortunately this method does not apply to cyclic configurations (vk), for v prime and is not certainly not understood well for k > 4. I am not sure what happens if pseudolines are admitted in such drawings having rotational symmetry.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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