The Nauru graph is the name given by Eppstein (2007) to the generalized Petersen graph 
on 24 vertices 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. It is illustrated above
in a number of embeddings.
The name of the graph derives from the resemblance of the central star polygon in a generalized Petersen graph embedding to the 12-point star on the flag of the Pacific island nation known internationally as Nauru prior to its 2026 name change to Naoero.
The Nauru graph is one of three cubic graphs on 24 vertices 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. 2020). It also has rectilinear crossing number 8. A number of minimal crossing embeddings are shown 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"].
