Constructions of large graphs on surfaces
Feria-Puron, Ramiro, Pineda-Villavicencio, Guillermo · 2013
We consider the degree/diameter problem for graphs embedded in a surface, namely, given a surface Σ and integers Δ and k, determine the maximum order N(Δ,k,Σ) of a graph embeddable in Σ with maximum degree Δ and diameter k. We introduce a number of constructions which produce many new largest known planar and toroidal graphs. We record all these graphs in the available tables of largest known graphs.