Regular and Strongly Regular Planar Graphs

Abstract

We give a constructive proof that a planar graph on $n$ vertices with degree of regularity $k$ exists for all pairs $(n,k)$ except for two pairs $(7,4)$ and $(14,5)$. We continue this theme by classifying all strongly regular planar graphs, and then consider a new class of graphs called $2$-\emph{strongly regular}. We conclude with a conjectural classification of all planar $2$-strongly regular graphs.