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 $$sqrt{frac{3}{8}}g Delta^{lfloor k/2 rfloor}.$$ Our constructions produce new graphs of order $$left{begin{array}{ll}6 Delta^{lfloor k/2 rfloor} qquad qquad qquad qquad {rm if Sigma;is;the;Klein;bottle} left(frac{7}{2} + sqrt{6g + frac{1}{4}}right) Delta^{lfloor k/2 rfloor} quad {rm otherwise},end{array}right.$$ thus improving the former value.