Constructions of Large Planar Graphs with Given Diameter and Maximum Degree
Karen Seyffarth
University of Calgary

The problem of constructing large graphs (networks) with given diameter and maximum degree has generated considerable interest. In some applications, planarity is a natural restriction on the networks, and thus we consider the problem of determining $p(\Delta,k)$, the maximum number of vertices in a planar graph with maximum degree $\Delta$ and diameter at most $k$. We will begin with a survey of what is known about $p(\Delta,k)$, and then describe a number of general constructions that yield, for given $\Delta$ and $k$, the largest known planar graphs. We also present, for small values of $\Delta$ and $k$, some of the largest know graphs, mostly obtained by ad-hoc constructions.