Crossing Number (Ed Pegg Jr) | Discuss about this problem | ||||||||||||||||||||||||||||
In recent work with Geoff Exoo, the crossing numbers of cubic symmetric graphs have been record-setters. So far, no smaller cubic graphs have had higher crossing numbers. Each of the graphs above 6 vertices also has at least one irregular two with the same vertex count and CR. See the center image of DesarguesGraph for an image on how to draw it with 6 crossings (found by Ed Pegg Jr).
Might be interesting to have a contest that extended the crossing numbers of the cubic symmetrics. As part 2 of scoring, let the closest vertices be distance 1 apart -- what is the size of the entire graph ? For a given graph, what is the smallest number of edge crossings? For CR 0 to CR 6, the smallest graphs are cubic symmetric graphs. |