The Nauru graph is the name given by Eppstein (2007) to the generalized Petersen graph on 24 nodes and 36 edges which is also cubic symmetric graph , the permutation star graph of order 4, the honeycomb toroidal graph , the Levi graph of the Coxeter configuration (perhaps better termed the "Nauru configuration"), and the rolling polyhedron graph for the regular octahedron.
The name of the graph derives from the resemblance of the central star polygon in the generalized Petersen embedding to the 12-point star on the flag of the Pacific island nation of Nauru.
The Nauru graph is one of three cubic graphs on 24 nodes with smallest possible graph crossing number of 8 (another being the McGee graph), making it a smallest cubic crossing number graph (Pegg and Exoo 2009, Clancy et al. 2019). It also has rectilinear crossing number 8. A number of minimal crossing embeddings are show above.
The configurations of a Rubik's cube reachable using only half twists form a Nauru graph.
It is also a unit-distance graph, as illustrated above in a number of unit-distance embeddings. The first was given by itnik et al. (2010) and the second is due to Gerbracht (pers. comm., Jan. 4, 2010).
The Nauru graph is implemented in the Wolfram Language as GraphData["NauruGraph"].