Constructions of large graphs on surfaces

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. Given a surface Σ of Euler genus g and an odd diameter k, the current best asymptotic lower bound for N(Δ,k,Σ) is given by (Formula presented). Our constructions produce new graphs of order (Formula presented) thus improving the former value. © 2013 Springer Japan.