The degree-diameter problem involves finding a possible graph G with the largest number of vertices p(Δ, D), where Δ is the maximum degree of G and D is the diameter of G. We know that the size of a possible graph is bounded by the Moore bound. However, the bound is usually much larger than the actual solution.

In this paper, the author investigates a special planar graph, with an even diameter D (D = 2d) and degree Δ large enough that Δ ≥ 6(12d + 1). The author analyzes the 5-separator construction for this kind of planar graph and obtains a lower bound for the maximum size. New graph examples are constructed as proof. When the maximum degree Δ ≥ 6(12d + 1), the author proves that the lower bound is exact. The result is much stronger than previous results.

The main contribution of this paper is the proof of an exact solution for the degree-diameter problem for a special planar graph with the stated parameters. The second contribution is the new constructions that are presented. The separator method considered in this paper may be useful for other graphs.