The Petersen graph was constructed by Kempe (1886) as the graph whose vertices correspond to the points of the Desargues configuration and edges to pairs of points that do not lie on lines that are part of the configuration. The graph at right corresponds to this construction and, though not immediately apparent from its embedding, it is in fact isomorphic to the Petersen graph.
Graphs produced from configurations in this way have been termed ordinary (line) graphs by Ed Pegg, Jr. (pers. comm., Sep. 11, 2024) as a result of the fact that the edges of such graphs correspond to ordinary lines of the underlying configuration.
Note that to avoid inclusion of collinear and overlapping edges, line segments corresponding to pairs of vertices that lie along all extraordinary lines, including any that might not be part of the original configuration, are not allowed. For example, the left illustration above shows a version of the ordinary line graph of the Grünbaum-Rigby configuration in which edges corresponding to line segments along the seven lines passing through three points (that are not part of the configuration) are included, while the right figure shows the "proper" ordinary line graph excluding such edges.
Ordinary line graphs generated by a number of named configurations are illustrated above.
The following table summarizes some configurations with named ordinary line graphs.
configuration | ordinary line graph |
configuration 1 | |
configuration 2 | cycle graph |
Coxeter configuration | 28-noncayley vertex-transitive graph 61 |
Cremona-Richmond configuration | triangular graph |
Desargues configuration | Petersen graph |
hexagram configuration | 12-vertex-transitive graph 27 |
Nauru configuration | rook graph |
octagram configuration | Shrikhande graph |
Pappus configuration | |
pentagram configuration | Petersen graph |
Reye configuration |