\documentclass[12pt]{article} \usepackage{e-jc} %\usepackage[english]{babel} \usepackage{amsthm,amsmath,amssymb} \usepackage{graphicx} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{\bf The degree/diameter problem in maximal planar bipartite graphs} \author{Cristina Dalf\'{o}\thanks{Research supported by the Ministry of Education and Science, Spain, and the European Regional Development Fund under project MTM2014-60127-P, and by the Catalan Research Council under project 2014SGR1147.}\\ \small Departament de Matem\`{a}tiques\\[-0.8ex] \small Universitat Polit\`{e}cnica de Catalunya, BarcelonaTech\\[-0.8ex] \small Barcelona, Catalonia\\ \small\tt cristina.dalfo@upc.edu\\ \and Clemens Huemer\thanks{Research partially supported by project %s MEC MTM2012-30951 and Gen. Cat. DGR %2009SGR1040, 2014SGR46 % and ESF EUROCORES programme EuroGIGA, CRP ComPoSe: grant EUI-EURC-2011-4306 .}\\ \small Departament de Matem\`{a}tiques\\[-0.8ex] \small Universitat Polit\`{e}cnica de Catalunya, BarcelonaTech\\[-0.8ex] \small Barcelona, Catalonia\\ \small\tt clemens.huemer@upc.edu\\ \and Juli\'{a}n Salas\thanks{Research partial supported by the Spanish MEC project ICWT (TIN2012-32757).}\\ \small Dept. of Computer Engineering and Mathematics\\[-0.8ex] \small Universitat Rovira i Virgili\\[-0.8ex] \small Tarragona, Catalonia, Spain\\ \small\tt julian.salas@urv.cat\\ } \date{\dateline{Jun 1, 2014}{Jun 2, 2014}\\ \small Mathematics Subject Classifications: 05C10} \begin{document} \maketitle \begin{abstract} The $(\Delta,D)$ (degree/diameter) problem consists of finding the largest possible number of vertices $n$ among all the graphs with maximum degree $\Delta$ and diameter $D$. We consider the $(\Delta,D)$ problem for maximal planar bipartite graphs, that is, simple planar graphs in which every face is a quadrangle. We obtain that for the $(\Delta,2)$ problem, the number of vertices is $n=\Delta+2$; and for the $(\Delta,3)$ problem, $n= 3\Delta-1$ if $\Delta$ is odd and $n= 3\Delta-2$ if $\Delta$ is even. Then, we prove that, for the general case of the $(\Delta,D)$ problem, an upper bound on $n$ is approximately $3(2D+1)(\Delta-2)^{\lfloor D/2\rfloor}$, and another one is $C(\Delta-2)^{\lfloor D/2\rfloor}$ if $\Delta\geq D$ and $C$ is a sufficiently large constant. Our upper bounds improve for our kind of graphs the one given by Fellows, Hell and Seyffarth for general planar graphs. We also give a lower bound on $n$ for maximal planar bipartite graphs, which is approximately $(\Delta-2)^{D/2}$ if $D$ is even, and $3(\Delta-3)^{D/2}$ if $D$ is odd, for $\Delta$ and $D$ sufficiently large in both cases. \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% s e c c i ó 1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} We consider simple graphs $G=G(V,E)$ that are bipartite, planar and with the maximum possible number of edges. In a \emph{bipartite} graph, each cycle has even length. If a graph can be drawn on the plane without any crossing of its edges, then the graph is called \emph{planar}. A planar bipartite graph is maximal if when we add a new edge, the graph obtained is no longer planar or bipartite. A maximal planar bipartite graph divides the plane only into quadrangles (see Ringel~\cite{Ri93}). As a notation, in a bipartite graph we denote the two partition classes with colors black $B$ and white $W$. Then $n=|B|+|W|$. From the Euler characteristic $|V|-|E|+|F|=2$, which relates the numbers of vertices $n=|V|$, edges $|E|$ and faces $|F|$ in a planar embedding of $G$, and the fact that each face is incident to four edges, one obtains the well-known relations $|E|=2n-4$ and $|F|=n-2$. The $(\Delta,D)$ problem consists of finding the maximum possible number of vertices $n=|V|$ in a graph $G$ with maximum degree $\Delta$ and diameter $D$. This is a prominent topic in graph theory, with results obtained for many cases. Information about this problem for graphs in general can be found in the comprehensive survey by Miller and \v{S}ir\'{a}\v{n}~\cite{MiSi13} and for planar graphs also on the web page by Loz, P\'{e}rez-Ros\'{e}s, and Pineda-Villavicencio~\cite{LoPRPV13}. The $(\Delta,D)$ problem for maximal bipartite planar graphs belongs to the area of construction of large planar graphs, and of large maximal planar graphs, with given diameter and maximum degree. Bipartiteness is added as a natural restriction.\\ For simple maximal planar graphs (that is, triangulations), the $(\Delta,D)$ problem with diameter $D=2$ and $\Delta\geq 8$ was solved by Seyffarth in~\cite{Se89}. She proved that, in this case, the number of vertices is $n\leq \lfloor\frac{3}{2}\Delta\rfloor+1$ if $\Delta\geq8$, and that this bound is best possible. Later, Hell and Seyffarth~\cite{HeSe93} showed that this result also holds for the larger class of all simple planar graphs. Yang, Lin, and Dai~\cite{YaliDa02} solved the remaining case $\Delta<8$ with $D=2$, for both graph classes. Fellows, Hell and Seyffarth~\cite{FeHeSe95} found that an upper bound on the number of vertices for planar graphs is $8\Delta+12$ for diameter $D=3$, and $3(2D+1)(2\Delta^{\lfloor D/2\rfloor}+1)$ for any diameter. Regarding lower bounds on the maximum number of vertices of planar graphs, given a fixed diameter $D$ and a maximum degree $\Delta$, Fellows, Hell and Seyffarth~\cite{FeHeSe98} proved that $n~\geq~\frac{9}{2}\Delta^{(D-1)/2}-o(\Delta^{(D-1)/2})$ for odd $D$, and $n \geq \frac32 \Delta^{D/2}-o(\Delta^{D/2})$ for even $D$. % presented a complete $(\Delta-1)$-ary tree of height $\lfloor D/2\rfloor$ to obtain $n\geq\frac{\Delta}{\Delta-2}[(\Delta-1)^{\lfloor D/2\rfloor}-1]$. Later, Feria-Puron and Pineda-Villavicencio~\cite{FPPV13} presented a lower bound on the maximum number of vertices for planar graphs of maximum degree $\Delta\geq6$ and odd diameter $D\geq5$, which is $\left(\left\lfloor\frac{9\Delta}{2}\right\rfloor-12\right)\frac{\Delta(\Delta-1)^{(D-3)/2}-2}{\Delta-2}+9$. For planar graphs with even diameter $D=2k$ and maximum degree $\Delta$, Tishchenko~\cite{Ti12} obtained the lower bound $\left\lfloor\frac{3\Delta}{2}\,\frac{(\Delta-1)^k-1}{\Delta-2}\right\rfloor+1$, and proved that this is also an upper bound for cases with large $\Delta$, concretely for~$\Delta~\geq~6(12~k~+~1~)$. Related bounds on the $(\Delta,D)$ problem for sparse graph classes and for graphs embedded on surfaces can be found in Nevo, Pineda-Villavicencio and Wood~\cite{NePiWo13}, and Pineda-Villavicencio and Wood~\cite{PiWo13}. In particular, in~\cite{PiWo13} the following upper bounds on the number $n$ of vertices in a graph with diameter $D$ and maximum degree $\Delta$ are proved: \begin{itemize} \item Graphs with arboricity $b$: $n\leq 4D(2b)^D \Delta^{\lfloor{D/2}\rfloor}+1$. \item Graphs with treewidth $t$: $n\leq (3+\epsilon)(t+1)(\Delta-1)^{(D-1)/2}$ if $D$ is odd, for $\epsilon>0$, and $\Delta \geq $ some constant $c_\epsilon$; $n\leq \left(\frac{3}{2}+\epsilon\right)\sqrt{t+1}(\Delta-1)^{D/2}$ if $D$ is even, for $\epsilon>0$, and $\Delta \geq c_\epsilon \sqrt{t+1}$. \item Graphs with average vertex degree $d$: $n \leq 2d(\Delta-1)^{D-1}+1.$ \end{itemize} In Nevo, Pineda-Villavicencio and Wood~\cite{NePiWo13}, it is shown that for graphs embeddable on a surface of Euler genus $g$: $$n \leq c(g+1)(\Delta-1)^{D/2} \ \mbox{if $D$ is even and $\Delta \geq c(g^{2/3}+1)D$ for some absolute constant $c$},$$ $$n \leq c(g^{3/2}+1)(\Delta-1)^{\lfloor D/2 \rfloor} \ \mbox{if $D$ is odd and $\Delta \geq 2D+1$ for some absolute constant $c$}.$$ For the class of bipartite graphs, see Miller and \v{S}ir\'{a}\v{n}~\cite{MiSi13}, $n \leq \frac{2(\Delta-1)^D-1}{\Delta-2} \ \mbox{for $\Delta >2$.}$\\ In this paper, we consider the $(\Delta,D)$ problem for maximal planar bipartite graphs. We remark that these graphs have arboricity two, unbounded treewidth, average vertex degree $4-\frac{8}{n}$, and can be embedded on a surface of genus $g=0$. \begin{figure}[t] \centering \includegraphics[scale=0.7]{bipartitemaximal18.pdf} \caption{Two graphs with diameter $D=3$ and maximum vertex degree $\Delta=6$: A maximal planar bipartite graph with $n=16$ vertices (left) and a planar bipartite graph with $n=18$ vertices (right).} \label{fig:bipartitemaximal18} \end{figure} We show in Section~\ref{sec:2}, that in the $(\Delta,2)$ problem $n=\Delta+2$ and that only the complete bipartite graph $K_{2,\Delta}$ satisfies this equation. Moreover, we solve the $(\Delta,3)$ problem and prove that $n= 3\Delta-1$ if $\Delta$ is odd, and $n= 3\Delta-2$ if $\Delta$ is even, and we give examples of graphs that satisfy these equations. In Section~\ref{sec:3}, we study the general case $(\Delta,D)$ and obtain that $n$ is bounded from above by approximately $3(2D+1)(\Delta-2)^{\lfloor D/2\rfloor}$. %, for sufficiently large $\Delta$ and $D$. For the case $\Delta\geq D$ we also obtain the upper bound $n\leq C(\Delta-2)^{\lfloor D/2\rfloor}$, for some constant $C$. Our upper bound improves for our kind of graphs the one given by Fellows, Hell and Seyffarth~\cite{FeHeSe95} for general planar graphs, and those given by Nevo, Pineda-Villavicencio and Wood~\cite{NePiWo13}, and by Pineda-Villavicencio and Wood~\cite{PiWo13}, for the above mentioned more general classes, when $\Delta$ is small with respect to $D$. However, when $\Delta$ is much larger than the diameter, our improvement is, asymptotically, just marginal ($\Delta-1$ is replaced with $\Delta-2$). For the proof we derive a Moore-type bound for maximal planar bipartite graphs (which gives a weak upper bound on the number $n$ of vertices), and then follow the approach of Fellows, Hell and Seyffarth~\cite{FeHeSe95}, which makes use of the Lipton-Tarjan separator theorem~\cite{LiTa79}. The obtained bound is then improved by using the $N$-separator theorem by Tishchenko~\cite{Ti12, Ti12a} instead of the separator theorem by Lipton and Tarjan.\\ We also give a lower bound on $n$ for maximal planar bipartite graphs, which is approximately $(\Delta-2)^{k}$ if $D=2k$, and $3(\Delta-3)^k$ if $D=2k+1$, for $\Delta$ and $D$ sufficiently large in both cases. The precise bounds are given in this section. %An exact solution for the $(\Delta,2)$ problem and for the $(\Delta,3)$ problem is presented. For large diameter $D$ we determine the maximum number $n$ of vertices asymptotically; more precisely we show that there exist two positive constants $C$ and $C'$ such that for even diameter $D$, the maximum number of vertices $n$ satisfies $C'(\Delta-2)^{D/2} \leq n \leq C(\Delta-2)^{D/2}$ for $\Delta$ and $D$ large enough.\\ Let us compare these results with the $(\Delta,D)$ problem for maximal planar graphs (which are not bipartite). In this case, an exact solution is known for diameter $D=2$. And for large diameter $D$, the known upper bound is the one obtained for the class of planar graphs, which is $n \leq C(\Delta-1)^{D/2}$ for $D$ large enough and $C$ a constant. The maximum number of vertices for the $(\Delta,D)$ problem for maximal planar graphs might be smaller.\\ It is also interesting to compare the $(\Delta,D)$ problem for maximal bipartite graphs with the same problem for planar bipartite graphs (which are not necessarily maximal). To our knowledge, this problem, which was raised by a reviewer, has not been considered so far. Already for diameter $D=3$ the solutions of the $(\Delta,D)$ problem are different. Figure~\ref{fig:bipartitemaximal18} shows, for even $D$, a maximal planar bipartite graph that has the maximum number of vertices $n=3\Delta-2$ (left) and a planar bipartite graph that has $n=3\Delta$ vertices (right). For large diameter $D$, there are planar bipartite graphs with $C(\Delta-1)^{D/2}$ vertices, which is the bound for the class of planar graphs. An example for this bound (with even diameter $D$) can be obtained by gluing two trees of radius $D/2$, in the same way as done in the proof of Theorem~\ref{thm:lowerBound}(a).\\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% s e c c i ó 2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{The $(\Delta,2)$ and $(\Delta,3)$ problems in maximal planar bipartite graphs} \label{sec:2} For maximal planar bipartite graphs with diameter $D=2$, we solve the $(\Delta,2)$ problem with the following result. \begin{proposition} Consider a maximal planar bipartite graph $G$ with diameter $D=2$, maximum degree $\Delta$ and maximum number of vertices $n$, then $n=\Delta+2$. The only graph that satisfies this equation is the complete bipartite graph $K_{2,\Delta}$. \end{proposition} \begin{proof} For $\Delta=2$, there is no maximal planar bipartite graph with more than four vertices. The cycle on four vertices $C_4$ satisfies $n=\Delta+2.$ Therefore, let us assume that $\Delta>2$. Let $v$ be a vertex of degree $\Delta$ in $G$. Suppose, for the sake of contradiction, that there is more than one vertex at distance two from $v$ in $G$. Denote two such vertices by $w$ and $z$. Then, $w$ and $z$ are not both adjacent to all neighbors of $v$; otherwise $G$ would contain the complete bipartite graph $K_{3,3}$ as a subgraph, contradicting the planarity of $G$. Hence, there is a neighbor $u$ of $v$ incident to at most one of $w$ and $z$, say $u$ is not adjacent to $z$. The vertices $u$ and $z$ belong to different partite classes, which implies that the distance between them is odd. It follows that the distance between $u$ and $z$ is at least three, contradicting $D=2$. Thus, $n=\Delta+2$ and only the complete bipartite graph $K_{2,\Delta}$ attains this bound. \end{proof} For maximal planar bipartite graphs with diameter $D=3$, our main result is the following. \begin{theorem} \label{teorema:principal} Consider a maximal planar bipartite graph $G$ with diameter $D=3$, maximum degree $\Delta$ and maximum number of vertices $n$, then $$ n=\left\{ \begin{array}{ll} 3\Delta-1 & \mbox{if $\Delta$ is odd},\\ 3\Delta-2 & \mbox{if $\Delta$ is even}. \end{array} \right. $$ %This bound is best possible. \end{theorem} %In order to prove this result, we state some lemmas, which are needed in the proof of this theorem. The proof of this result is implied by some lemmas, which we state below. The following observation will be used throughout. \begin{observation}\label{obs:neighbor} In a bipartite graph with diameter $D=3$, any two vertices from the same bipartition class have at least one common neighbor from the other bipartition class. \end{observation} First we study the cases $\Delta=3$ and $\Delta=4$. \begin{lemma}\label{prop:eight} If $G$ is a maximal planar bipartite graph with maximum degree $\Delta=3$, then $n\leq8$. This bound is best possible. \end{lemma} \begin{proof} Adding up all the vertex degrees of $G$, we get $$2|E|=\sum_{v \in G} \deg(v) \leq n \Delta .$$ Since $|E|=2n-4$, we obtain the claimed bound $n(4-\Delta)\leq 8$. A graph that attains this bound, with diameter $D=3$, is the cube. \end{proof} \begin{lemma} \label{lema:n=2Delta+2} Let $G$ be a maximal planar bipartite graph with diameter $D=3$, maximum degree $\Delta$, and $n$ vertices. If $G$ contains a vertex that has at least four neighbors of degree $d>2$, then $n\leq2\Delta+2$. \end{lemma} \begin{proof} Let $v$ be a vertex of $G$ that has at least four neighbors of degree at least $3$. Denote by $n'$ the number of these neighbors of $v$. Let the color of $v$ be white. Consider a planar embedding of $G$ and consider the region $R_v$ formed by all the faces incident to $v$. Region $R_v$ is delimited by a cycle $C_v$ with $2n'\geq 8$ vertices, see Figure~\ref{fig:degree4vertexAltreCas} (left). Moreover, cycle $C_v$ has no chords. Also, there can be more vertices of degree two incident to $v$ (which are not drawn in the figure). Observe that, after removing one of these vertices of degree two from the interior of $R_v$, the graph is still a maximal planar bipartite one. %(consider the smallest cycle with at least $2n'$ vertices that contains $v$). The cycle $C_v$ has $n'$ white vertices (denoted by $a_1,a_2,b_1$ and $b_2$ in the figure). In order to have distance two between any pair of white vertices of $C_v$, connections outside $R_v$ must exist (in the figure, there must be a black vertex outside $R_v$ which is incident to vertices $a_1$ and $a_2$, and a black vertex outside $R_v$ which is incident to vertices $b_1$ and $b_2$). The only possibility to avoid crossings is that all white vertices of $C_v$ are incident to a common black vertex, denoted by $w$ in the figure, outside $R_v$. Now, all remaining vertices of the graph lie in the faces (including the outer face) defined by the subgraph $G'$ of $G$ that is induced by $C_v$ and vertices $v$ and $w$. Because of Observation~\ref{obs:neighbor}, none of the faces of $G'$ incident to $v$ can contain a white vertex, and none of the faces incident to $w$ can contain a black vertex. This implies that only vertices of degree two can be added to $G'$, all black ones must be incident to $v$ and all white ones must be incident to $w$. Since the degree of $v$ and $w$ in $G$ is at most $\Delta$, at most $\Delta-n'$ white vertices and $\Delta-n'$ black vertices can be added. We conclude that $G$ has at most $2+2n'+2(\Delta-n')=2\Delta+2$ vertices. \end{proof} \begin{lemma}\label{prop:ten} If $G$ is a maximal planar bipartite graph with diameter $D=3$, maximum degree $\Delta=4$ and $n$ vertices, then $n\leq10$. This bound is best possible. \end{lemma} \begin{proof} First, consider the case in which $G$ contains no $K_{2,3}$ as a subgraph. Then $G$ contains no vertex of degree $2$. Otherwise, in a planar embedding of $G$, the two faces incident to a vertex $v$ of degree $2$ together contain five vertices, forming a $K_{2,3}$, see Figure~\ref{fig:degree4vertexAltreCas} (right). Therefore, as $\Delta=4$, $G$ satisfies the conditions of Lemma~\ref{lema:n=2Delta+2} and $n\leq 10$.\\ Next, consider the case in which $G$ contains at least two copies of the complete bipartite graph $K_{2,3}$ as a subgraph, one $K_{2,3}$ with two white vertices and three black ones, and the other one with three white vertices and two black ones. Take into account the copy of $K_{2,3}$ with two white vertices, denoted by $x$ and $y$. We claim that each black vertex $v$ of $G$ has to be adjacent to at least one of $x$ and $y$. To prove this, considering a planar embedding of $G$, vertex $v$ lies in one of the three regions determined by $K_{2,3}$, such that each region is bounded by a 4-cycle. Moreover, by Observation~\ref{obs:neighbor}, vertex $v$ is at distance two from the three black vertices of $K_{2,3}$. Therefore, $v$ is incident to at least one of $x$ and $y$. Maximum degree $\Delta=4$ implies that at most one more black vertex can be incident to $x$, and at most one more incident to $y$. Thus, $G$ contains at most $5$ black vertices. The symmetric argument for the other color class shows that $G$ contains at most $5$ white vertices. This completes the proof of this case.\\ Finally, consider the case when $G$ contains a $K_{2,3}$ as a subgraph with two white vertices and three black vertices, and $G$ contains no $K_{2,3}$ as a subgraph with two black vertices and three white ones. (The other case interchanging colors is symmetric.) If $G$ contains a black vertex of degree $\Delta=4$, then none of its neighbors has degree $2$ (otherwise, we would have a $K_{2,3}$), and applying Lemma~\ref{lema:n=2Delta+2} we obtain $n\leq 10$. Therefore, we can assume no black vertex has degree greater than $3$. Repeating the argument from the previous case, we get that $G$ contains at most $5$ black vertices. But then, comparing the number of edges with the sum of the vertex degrees of the black vertices, we get $$2n-4=\sum_{v \in B}\deg(v) \leq (\Delta-1) \cdot 5=15,$$ which yields $n\leq 9$.\\ A graph attaining the bound $n=10$ is shown in Figure~\ref{fig:degree4vertexAltreCas} (left). \end{proof} \begin{figure}[t] \vskip-.5cm \begin{center} \includegraphics[width=15cm]{grau4bis.pdf} \end{center} \vskip-17cm \caption{Connecting the white vertices $a_1,a_2,b_1$ and $b_2$ on cycle $C_v$ through a black vertex $w$ outside region $R_v$ (left), and a $K_{2,3}$ (right).} \label{fig:degree4vertexAltreCas} \end{figure} \begin{lemma} \label{lema:n-8vertexsgrau2} Let $G$ be a maximal planar bipartite graph with diameter $D=3$ and maximum degree $\Delta$. If $G$ does not contain a vertex that has at least four neighbors of degree $d>2$, then $G$ has at least $n-8$ vertices of degree $2$. \end{lemma} \begin{proof} Let $n$ be the number of vertices of $G$ and let $n_i$ be the number of vertices of degree $i$ in $G$, for $2\leq i\leq\Delta$. We have $$\sum_{i=2}^{\Delta}n_i=n,$$ and since $G$ has $2n-4$ edges, $$\sum_{i=2}^{\Delta}i n_i=2(2n-4).$$ For each vertex $v$, at most three of its neighbors have degree at least 3 and the other neighbors have degree 2. Thus, every vertex of degree $i\geq 4$ is incident to at least $i-3$ vertices of degree $2$. Therefore, $$2n_2 \geq \sum_{i=4}^{\Delta}(i-3)n_i.$$ Then $$\sum_{i=4}^{\Delta}(i-3)n_i=\left(\sum_{i=2}^{\Delta}(i-3)n_i\right)+n_2=\left(\sum_{i=2}^{\Delta}i n_i\right)-\left(\sum_{i=2}^{\Delta}3n_i\right)+n_2=2(2n-4)-3n+n_2.$$ It follows that $n_2\geq n-8$. \end{proof} We are now ready to finish the proof of Theorem~\ref{teorema:principal} with the following lemma, which completes the case $\Delta\geq5$. \begin{lemma} \label{lema:n<=3Delta-1} Let $G$ be a maximal planar bipartite graph with diameter $D=3$, maximum degree $\Delta\geq 5$ and $n$ vertices. If $G$ contains at least $n-8$ vertices of degree $2$, then $n\leq 3\Delta-1$ if $\Delta$ is odd, and $n\leq 3\Delta-2$ if $\Delta$ is even. \end{lemma} \begin{proof} Removing a vertex of degree $2$ from a maximal planar bipartite graph on $n$ vertices gives a maximal planar bipartite graph on $n-1$ vertices. Hence, we can (simultaneously) remove vertices of degree $2$ from $G$ to obtain a maximal planar bipartite graph $G'$ with at most $n'=8$ vertices. Consider a planar embedding of $G'$. By the Euler characteristic, the number of faces in this embedding of $G'$ is at most $n'-2=6$. Graph $G$ is obtained again from $G'$ by inserting the vertices of degree $2$. Therefore, in each face of $G'$ only vertices of one color class can be inserted. We assign the corresponding color (white or black) to the faces of $G'$. Faces of $G'$ with no vertices of $G$ in its interior get no color assigned. There are $w$ white faces $\{w_1,\ldots,w_w\}$ and $b$ black faces $\{b_1,\ldots,b_b\}$ in $G'$, with $w+b\leq n'-2$. For $1\leq i \leq w$, let $n_2(w_i)$ be the number of vertices of degree two of $G$ in face $w_i$, and for $1\leq j \leq b$ let $n_2(b_j)$ be the number of vertices of degree two of $G$ in face $b_j$. Observation~\ref{obs:neighbor} implies that each pair of faces of $G'$ (with vertices of $G$ in its interior) with the same color assigned must share a vertex $v$ of $G'$, and all the vertices of degree $2$ of $G$ in the interior of these two faces are incident to $v$. We now distinguish cases according to the number of white faces. We can assume, without loss of generality, that $w\geq b$. \begin{figure}[t] \vskip-.75cm \begin{center} \includegraphics[width=12cm]{grau3.pdf} \end{center} \vskip-5cm \caption{Case (1): $w=3$}\label{fig:degree3} \end{figure} \emph{Case (1): $w=3$:} First consider the subcase when all three white faces share a common vertex $v$ such that all the white vertices of degree two in $G\setminus G'$ are incident to $v$, see Figure~\ref{fig:degree3} (left). In Figures~\ref{fig:degree3} and \ref{fig:degree 4}, the thick lines define the white faces. Vertex $v$ has degree at least three in $G'$. Then, \begin{equation}\label{eq:case1} n_2(w_1)+n_2(w_2)+n_2(w_3)\leq \Delta-3. \end{equation} The only other possible subcase is depicted in Figure~\ref{fig:degree3} (right). Consider the black vertices of the white faces, which are incident to vertices of degree two in $G\setminus G'$. If none of them is incident to all three white faces, then there must exist three vertices $x,y$ and $z$ which pairwise determine the three white faces. Namely, the vertices $x,y$ determine the first face, the vertices $x,z$ determine the second face, and the vertices $y,z$ determine the third face. This follows from the fact that every two white faces must share a black vertex incident to vertices of degree two in $G\setminus G'$. (However it is not necessary that the three white faces share a common white vertex of $G'$.) We also observe that the degree of each of the vertices $x,y$ and $z$ is at least three in $G'$. Then, \begin{equation*} \begin{split} n_2(w_1)+n_2(w_2) &\leq \ \Delta-3, \\ n_2(w_1)+n_2(w_3) &\leq \ \Delta-3, \\ n_2(w_2)+n_2(w_3) &\leq \ \Delta-3. \end{split} \end{equation*} Adding up these three inequalities, dividing by $2$, and since $n_2(w_1)+n_2(w_2)+n_2(w_3)$ is an integer, we have \begin{equation}\label{eq:case2} n_2(w_1)+n_2(w_2)+n_2(w_3)\leq \left\lfloor\frac{3\Delta-9}{2}\right\rfloor. \end{equation} Comparing Inequations~(\ref{eq:case1}) and~(\ref{eq:case2}), we get that in either subcase it holds $$n_2(w_1)+n_2(w_2)+n_2(w_3)\leq \left\lfloor\frac{3\Delta-9}{2}\right\rfloor.$$ % Now, if there are $b=3$ black faces, then we analogously obtain $$n_2(b_1)+n_2(b_2)+n_2(b_3)\leq \left\lfloor\frac{3\Delta-9}{2}\right\rfloor.$$ Otherwise, if there are at most two black faces, then all the black vertices of degree two in $G\setminus G'$ are incident to a common white vertex (with degree at least two in $G'$) and we have that, for $\Delta \geq 5$, $$\sum_{j=1}^{b}n_2(b_j) \leq \Delta -2 \leq \left\lfloor\frac{3\Delta-9}{2}\right\rfloor.$$ We conclude that%, for $\Delta\geq 6$, $$n=n'+\sum_{i=1}^{w}n_2(w_i)+\sum_{j=1}^{b}n_2(b_j) \leq 8+ 2 \left\lfloor\frac{3\Delta-9}{2}\right\rfloor \leq \left\{ \begin{array}{ll} 3\Delta-1 & \mbox{if $\Delta$ is odd},\\ 3\Delta-2 & \mbox{if $\Delta$ is even}. \end{array} \right.$$ %For the case $\Delta=5$ this bound also holds. Either there are $b=3$ black faces, in which case we also obtain %$$n = n' +\sum_{i=1}^{w}n_2(w_i)+\sum_{j=1}^{b}n_2(b_j) \leq 8+2 \frac{3\Delta-9}{2} = 3\Delta-1,$$ %or there are at most $b=2$ black faces, in which case we get %$$n = n' +\sum_{i=1}^{w}n_2(w_i)+\sum_{j=1}^{b}n_2(b_j) \leq 8+\Delta-2+\frac{3\Delta-9}{2} =14 = 3\Delta-1.$$ \begin{figure}[t] \vskip-.75cm \begin{center} \includegraphics[width=12cm]{grau3bis.pdf} \end{center} \vskip-5cm \caption{Case (2): $w\geq4$} \label{fig:degree 4} \end{figure} \emph{Case (2): $w\geq4$:} Figure~\ref{fig:degree 4} illustrates the two possible cases. On the left, all white faces share a common vertex $v$ such that all the white vertices of degree two in $G\setminus G'$ are incident to $v$. The degree of $v$ is at least $4$ in $G'$. Then, \begin{equation}\label{eq:case3} \sum_{i=1}^{w}n_2(w_i)\leq \Delta-4. \end{equation} Figure~\ref{fig:degree 4} (right) shows the other case, in which no black vertex is incident to all white vertices of degree two in $G\setminus G'$. Let $x$ and $y$ be the two black vertices of $G'$ of a white face. We claim that $\deg(x)+\deg(y)$ in $G'$ is at least $7$. For the white face containing $x$ and $y$ we count four edges of $G'$ incident to $x$ or $y$. Then, for each other white face there is at least one more edge of $G'$ incident to $x$ or $y$. (Again, we use that every vertex of degree two in $G\setminus G'$ is incident to at least one of $x$ and $y$; and therefore all ($\geq 4$) white faces are incident to at least one of $x$ and $y$.) Hence, one of $x$ and $y$, say $y$, has degree at least four in $G'$. The same argument holds for every other white face. Therefore, there exists another black vertex $z$ of a white face with degree at least $4$ in $G'$. Then, $z$ and $y$ lie in a common white face. Otherwise there would be at least four white faces incident to $y$ and another four white faces incident to $z$, contradicting the number of faces in $G'$ being at most $n'-2=6$. Hence, $y$ and $z$ are vertices of a common white face and $\deg(y)+\deg(z)$ in $G'$ is at least $8$. Since every white vertex of degree $2$ in $G$ is incident to at least one of $y$ and $z$, we have %Then there exists a third such vertex $z$ such that $x$ and $z$ belong to a white face and $y$ and $z$ belong to another white face. %(Analogous as in the Case 1) $r=3$.) The only way to add the fourth white face is to add it such that two of $x,y$ and $z$ are among its vertices. %In Figure~\ref{fig:degree 4} this fourth face is added to vertices $x$ and $y$. It follows that $x$ and $y$ together have degree at least $7$ in $G'$. %Also, all white vertices of degree two in $G$ are incident to at least one of $x$ and $y$. We thus have \begin{equation}\label{eq:case4} \sum_{i=1}^{w}n_2(w_i)\leq 2\Delta-8. \end{equation} Comparing Inequations~(\ref{eq:case3}) and~(\ref{eq:case4}), we have in either case $$\sum_{i=1}^{w}n_2(w_i)\leq 2\Delta-8.$$ Then, there are at most $b=2$ black faces in $G'$. All the black vertices of degree two in $G\setminus G'$ are incident to a common vertex (with degree at least two in $G'$) and we have $$\sum_{j=1}^{b}n_2(b_j) \leq \Delta -2.$$ We conclude $$n=n'+\sum_{i=1}^{w}n_2(w_i)+\sum_{j=1}^{b}n_2(b_j) \leq 8+ 2\Delta-8 + \Delta -2 \leq 3\Delta-2.$$ \emph{Case (3): $w\leq2$:} Note that two faces of the same color must share a vertex. This is deduced from Observation~\ref{obs:neighbor}. Therefore, all vertices of degree two of the same color of $G\setminus G'$ are incident to a common vertex. Therefore, $n \leq n'+ 2(\Delta-2) \leq 3\Delta-2$ for $\Delta \geq 6$ and $n\leq 3\Delta-1$ for $\Delta=5$. %Then, the only case corresponds to Figure XXX It remains to show that this bound can be attained. See four examples in Figure~\ref{fig:3Delta-1}. The general construction is obtained by adding vertices of degree 2 in the six faces of the cube. If $\Delta$ is odd, the number of vertices of degree 2 added is $\frac{\Delta-3}{2}$ in each face. For even values of $\Delta$, we add $\left\lceil\frac{\Delta-3}{2}\right\rceil$ vertices of degree $2$ in two faces and $\left\lfloor\frac{\Delta-3}{2}\right\rfloor$ in the others. In Section~\ref{sec:fita-inf} we give a proof that $D=3$ and we generalize this construction. This concludes the proofs of this lemma and also the one of Theorem~\ref{teorema:principal}. \end{proof} \begin{figure}[t] \vskip-.75cm \begin{center} \includegraphics[width=17cm]{3Delta-1.pdf} \end{center} \vskip-7.5cm \caption{Graphs with $n=3\Delta-1$: $(a): \Delta=3$ and $(c): \Delta=5$. Graphs with $n=3\Delta-2$: $(b): \Delta=4$ and $(d): \Delta=6$} \label{fig:3Delta-1} \end{figure} \section{The $(\Delta,D)$ problem in maximal planar bipartite graphs} \label{sec:3} \subsection{An upper bound} Fellows, Hell and Seyffarth~\cite{FeHeSe95} obtained bounds on the $(\Delta,D)$ problem for planar graphs applying the following theorem by Lipton and Tarjan~\cite{LiTa79}. \begin{theorem}[\cite{LiTa79}] \label{teorema:LiptonTarjan} Let $G$ be a planar graph on $n$ vertices containing a spanning tree of radius $r$. Then $V(G)$ can be partitioned into sets $A,B$ and $C$ such that no edges join vertices in $A$ with vertices in $B$, $|A|\leq\frac{2}{3}n$, $|B|\leq\frac{2}{3}n$, and $|C|\leq2r+1$. \end{theorem} Clearly, this theorem also holds for maximal planar bipartite graphs. We give an upper bound on the number of vertices for this kind of graphs. The cases $D=2$ and $D=3$ are studied in Section~\ref{sec:2}. No maximal planar bipartite graphs with $\Delta=3$ has more than $n=8$ vertices. Therefore, we assume that $D\geq4$ and $\Delta\geq4$. %, and we apply the same strategy as Fellows, Hell and Seyffarth~\cite{FeHeSe95} for this kind of graphs. \begin{theorem} \label{teorema:(Delta,D)} Let $G$ be a maximal planar bipartite graph on $n$ vertices with maximum degree $\Delta\geq4$ and diameter $D\geq4$. Then, \begin{itemize} \item[(a)] If $\Delta=4$: $n \leq 6(2D+1)\left({\left\lfloor\frac{D}{2}\right\rfloor}^2+{\left\lfloor \frac{D}{2}\right\rfloor}+1\right)$. \item[(b)] If $\Delta>4$: \begin{eqnarray} n &\!\!\!\!\!\!\!\leq\!\!\!\!\!\!\!& 3(2D+1) \left[\textstyle \frac{\sqrt{\Delta(\Delta-4)}}{2(\Delta-4)^{2}} \left[(\Delta-4+\sqrt{\Delta(\Delta-4)}\,)\left(\textstyle \frac{\Delta-2-\sqrt{\Delta(\Delta-4)}}{2}\right)^{\lfloor D/2\rfloor+1}\right.\right.\nonumber\\ && \left.\left.\left. \hskip-.25cm -2\sqrt{\Delta(\Delta-4)} + (4-\Delta+\sqrt{\Delta(\Delta-4)}\,)\textstyle \left(\frac{\Delta-2+\sqrt{\Delta(\Delta-4)}}{2}\right)^{\lfloor D/2\rfloor+1}\right] +2\right]\right.\!\!,\label{eq:fita-n-Delta>4} \end{eqnarray} which is approximately $3(2D+1)\left[\left(\Delta-2\right)^{\lfloor D/2\rfloor}+1\right]$ if $\Delta$ is sufficiently large. \end{itemize} \end{theorem} \begin{proof} As $G$ has diameter $D$, a spanning tree of $G$ has radius at most $D$. By Theorem~\ref{teorema:LiptonTarjan}, $V(G)$ can be partitioned into sets $A,B$ and $C$ such that no edges join vertices in $A$ with vertices in $B$, $|A|\leq\frac{2}{3}n$, $|B|\leq\frac{2}{3}n$, and $|C|\leq2D+1$. If some vertex $x$ in $A$ is at distance at least $\lfloor D/2\rfloor+1$ from every vertex in $C$, and some vertex $y$ in $B$ is at distance at least $\lfloor D/2\rfloor+1$ from every vertex in $C$, then the distance from $x$ to $y$ would be at least $2\lfloor D/2\rfloor+2>D$, which would contradict that the diameter of $G$ is $D$. Without loss of generality, we can assume that each vertex of $A$ is at distance at most $\lfloor D/2\rfloor$ from each vertex in $C$. Our aim is to give an upper bound on $n$, computing from each vertex of $C$ the maximum possible number of vertices at distance at most $\lfloor D/2\rfloor$. We build a subgraph adding vertices at distance $i$ from a given (root) vertex of $C$ in step $i$ $(0\leq i\leq\lfloor D/2\rfloor)$, to obtain a planar bipartite graph (which is almost maximal, meaning that all its interior faces are quadrangles), as shown in Figure~\ref{fig:arbre-esferic-Delta=4}. This is done in a similar way to the tree built to find the Moore bound (see Miller and \v{S}ir\'{a}\v{n}~\cite{MiSi13}). \begin{figure}[t] \vskip-.75cm \begin{center} \includegraphics[width=10cm]{arbre-esferic-Delta=4bis.pdf} \end{center} \vskip-8cm \caption{An almost maximal subgraph for $\Delta=4$} \label{fig:arbre-esferic-Delta=4} \end{figure} The case with $\Delta=4$ is as follows. Let $n_i$ be the number of vertices at distance $i$ (for $0\leq i\leq\lfloor D/2\rfloor$) from the root vertex. Then, $$ \begin{array}{rl} \mbox{step }0: & n_0=1 \\ \mbox{step }1: & n_1=4 \\ \mbox{step }2: & n_2=8\\ \mbox{step }3: & n_3=12\\ \vdots\mbox{\hskip.5cm} & \end{array} $$ Thus, $$ \sum_{i=0}^{\lfloor D/2\rfloor} n_i = 1+4\left(1+2+\cdots+\left\lfloor \frac{D}{2}\right\rfloor\right)= 1+2\left\lfloor \frac{D}{2}\right\rfloor\left(\left\lfloor \frac{D}{2}\right\rfloor+1\right). $$ Since $|B|\leq2n/3$, $|C|\leq2D+1$, and $|A|\geq n/3-(2D+1)$, so $$ \frac{n}{3}-(2D+1)\leq|A|\leq|C|\sum_{i=0}^{\lfloor D/2\rfloor} n_i\leq (2D+1)\left[1+2\left\lfloor \frac{D}{2}\right\rfloor\left(\left\lfloor \frac{D}{2}\right\rfloor+1\right)\right]. $$ Then, we obtain the upper bound $n\leq6(2D+1)\left({\lfloor\frac{D}{2}\rfloor}^2+{\lfloor\frac{D}{2}\rfloor}+1\right)$ for $\Delta=4$. For the case $\Delta>4$, the numbers of vertices $n_i$ at distance $i$ (for $0\leq i\leq\lfloor D/2\rfloor$) from the root vertex are $$ \begin{array}{rl} \mbox{step }0: & 1 \\ \mbox{step }1: & \Delta \\ \mbox{step }2: & (\Delta-2)\Delta\\ \mbox{step }3: & [(\Delta-2)\Delta](\Delta-2)-\Delta\\ \vdots\mbox{\hskip.5cm} & \end{array} $$ That is, the number of vertices $n_i$ follows the recurrence \begin{equation} n_i=(\Delta-2)n_{i-1}-n_{i-2}, \label{eq:rec} \end{equation} with $i>2$, $n_0=1$, $n_1=\Delta$, and $n_2=\Delta(\Delta-2).$ Indeed, in step $i>2$, $n_i$ is obtained by adding $\Delta-1$ vertices incident to each vertex of degree 1 after step $i-1$, and adding $\Delta-2$ vertices incident to each vertex of degree 2 after step $i-1$. In this computation, vertices added in step $i$ that belong to a quadrangle are counted twice, and there are $n_{i-1}$ of them. The number of vertices of degree 2 after step $i-1$ is $n_{i-2}$. The recurrence is immediate from these observations. We solve this recurrence equation with a generating function $G(z)$. For more information on generating functions, see for example Sedgewick and Flajolet~\cite{SeFl96}. Eq.~(\ref{eq:rec}) has $$ G(z) = \sum_{i\geq0}n_iz^i=\frac{n_0+(n_1-(\Delta-2)n_0)z}{1-(\Delta-2)z+z^2}, $$ for some initial values $n_0$ and $n_1$. For technical reasons, we consider $n_0=0$ and $n_1=\Delta$. Then, $G(z)=\frac{\Delta}{\alpha-\beta}\left(\frac{\alpha}{z-\alpha}-\frac{\beta}{z-\beta}\right)$, where $\alpha=\frac{1}{2}(\Delta-2+\sqrt{\Delta(\Delta-4)})$ and $\beta=\frac{1}{2}(\Delta-2-\sqrt{\Delta(\Delta-4)})$ for $\Delta>4$. Then, the solution of Eq.~(\ref{eq:rec}) with $n_0=0$ and $n_1=\Delta$ is \begin{equation} n_i=\frac{\Delta}{\sqrt{\Delta(\Delta-4)}}\left[\left(\frac{\Delta-2+\sqrt{\Delta(\Delta-4)}}{2}\right)^i- \left(\frac{\Delta-2-\sqrt{\Delta(\Delta-4)}}{2}\right)^i\right]. \label{eq:stepi} \end{equation} Thus, the total number of vertices $\displaystyle\sum_{i=0}^{\lfloor D/2\rfloor} n_i$ is obtained as the difference of two geometric series plus one unit, because our first term is $n_0=1$ instead of $n_0=0$: \begin{equation} \frac{\Delta}{\sqrt{\Delta(\Delta-4)}} \left(\frac{\left(\frac{\Delta-2+\sqrt{\Delta(\Delta-4)}}{2}\right)^{\lfloor D/2\rfloor+1}-1}{\frac{\Delta-2+\sqrt{\Delta(\Delta-4)}}{2}-1} - \frac{\left(\frac{\Delta-2-\sqrt{\Delta(\Delta-4)}}{2}\right)^{\lfloor D/2\rfloor+1}-1}{\frac{\Delta-2-\sqrt{\Delta(\Delta-4)}}{2}-1}\right)+1, \label{eq:suma} \end{equation} for $\Delta>4$ and $D\geq4$. Therefore, we have \begin{equation*} \begin{split} |A| \leq & \ |C| \sum_{i=0}^{\lfloor D/2\rfloor} n_i\\ = & \ |C| \left(\displaystyle\frac{\sqrt{\Delta(\Delta-4)}}{2(\Delta-4)^{2}} \left[(\Delta-4+\sqrt{\Delta(\Delta-4)}\,)\left(\frac{\Delta-2-\sqrt{\Delta(\Delta-4)}}{2}\right)^{\lfloor D/2\rfloor+1}\right.\right.\\ & \left.\left. -2\sqrt{\Delta(\Delta-4)} + (4-\Delta+\sqrt{\Delta(\Delta-4)}\,)\left(\frac{\Delta-2+\sqrt{\Delta(\Delta-4)}}{2}\right)^{\lfloor D/2\rfloor+1}\right] +1\right)\!\!. \end{split} \end{equation*} \begin{figure}[t] \vskip-.75cm \begin{center} \includegraphics[width=10cm]{grafica-n-D.pdf} \end{center} \vskip-0.5cm \caption{Plot of the log (base 10) of the number of vertices $n$ with respect to the diameter $D$ according to our bound given by Eq.~(\ref{eq:fita-n-Delta>4}) (black points) and the one by Fellows, Hell and Seyffarth given by Eq.~(\ref{eq:fita-FeHeSe}) (grey points), for $\Delta=5$ and $4\leq D\leq42$} \label{fig:grafica-n-D} \end{figure} As before, $|B|\leq2n/3$, $|C|\leq2D+1$, and $|A|\geq n/3-(2D+1)$. Then, \begin{equation*} \begin{split} n & \leq3(2D+1) \left[\left(\displaystyle\frac{\sqrt{\Delta(\Delta-4)}}{2(\Delta-4)^{2}} \left[(\Delta-4+\sqrt{\Delta(\Delta-4)}\,)\left(\frac{\Delta-2-\sqrt{\Delta(\Delta-4)}}{2}\right)^{\lfloor D/2\rfloor+1}\right.\right.\right.\\ & \left.\left.\left. \hskip-.25cm -2\sqrt{\Delta(\Delta-4)} + (4-\Delta+\sqrt{\Delta(\Delta-4)}\,)\left(\frac{\Delta-2+\sqrt{\Delta(\Delta-4)}}{2}\right)^{\lfloor D/2\rfloor+1}\right] +1\right)+1\right]\!\!. \end{split} \end{equation*} This expression gives an upper bound on the number of vertices for any $\Delta>4$ and $D\geq4$. We simplify it applying that $\sqrt{\Delta(\Delta-4)}\lesssim\Delta-2$. As $\Delta-2-\sqrt{\Delta(\Delta-4)}$ goes to 0 as $\Delta$ increases, we obtain \begin{equation*} %\begin{split} % n &<3(2D+1) \left[-\frac{\Delta}{\Delta-4} + \frac{(\Delta-2)^2}{(\Delta-4)^2}\left(\Delta-2\right)^{\lfloor D/2\rfloor} +1+1\right]\nonumber\\ % & =3(2D+1) \left[\frac{(\Delta-2)^2}{(\Delta-4)^2}\left(\Delta-2\right)^{\lfloor D/2\rfloor} -\frac{4}{\Delta-4}+1\right]< 3(2D+1) n \leq 3(2D+1) \left[\left(\Delta-2\right)^{\lfloor D/2\rfloor}+1\right]. %\end{split} \end{equation*} \end{proof} The upper bound given by Fellows, Hell and Seyffarth~\cite{FeHeSe95} for planar graphs is \begin{equation} \label{eq:fita-FeHeSe} n\leq3(2D+1)(2{\Delta}^{\lfloor D/2\rfloor}+1). \end{equation} As our graphs are planar, this bound also applies to maximal planar bipartite graphs, but our bound is much better for this kind of graphs. See an example for $\Delta=5$ in Figure~\ref{fig:grafica-n-D}, with the values of our bound given by Theorem~\ref{teorema:(Delta,D)} and the one by Fellows, Hell and Seyffarth.\\ We also give an alternative upper bound for the $(\Delta,D)$ problem of the form $n\frac{3N-1}{2}$. Then, an $N$-separator exists in $G$ such that $$ \min_{i\in (1,\ldots,N)}\left\{|V(A_i)|-\frac{1}{2}|V(B_i)| \right\} \geq \frac{1}{2N-1}\left(|V(G)|+ \frac{N-1}{2}\right). $$ \end{theorem} Now, applying the $N$-separator theorem by Tishchenko~\cite{Ti12, Ti12a}, we obtain the following result. \begin{theorem} There exists a constant $C$ such that each maximal planar bipartite graph $G$ with maximum degree $\Delta$ and diameter $D$, for $\Delta \geq D$, has at most $n\leq C (\Delta-2)^{\left\lfloor D/2\right\rfloor}$ vertices. \end{theorem} \begin{proof} Consider a planar embedding of $G$. We first extend $G$ to a triangulation $G_T$ by adding one auxiliary edge in each face of $G$. For $N=5$, let $S_5$ be the $5$-separator of $G_T$ obtained from Theorem~\ref{thm:nsep}. See Figure~\ref{fig:sepquad}. Since $G_T$ has diameter at most $D$, $S_5$ has at most $4(2D+1)$ edges and vertices. Then, the number of interior vertices $n(R_i)$ in each region $R_i$ is at least $$ n(R_i)=|V(A_i)|-|V(B_i)| \geq \frac{1}{2N-1}\left(|V(G)|+ \frac{N-1}{2}\right)-\frac{1}{2}|V(B_i)|\geq \frac{n-2}{9}-2(2D+1). $$ We claim that there exist two regions $R_i$ and $R_j$ that share at most two vertices. To prove the claim, we color the regions $R_i$ with four colors, so that regions that share a boundary edge have different colors; clearly, this can be done by the Four-Color Theorem (see Appel and Haken~\cite{ApHa77}, and also Robertson, Sanders, Seymour, and Thomas~\cite{RoSaSeTh96}). Therefore, there exist two regions $R_a$ and $R_b$ that do not share a common boundary edge. If $R_a$ and $R_b$ have at most two common vertices, then the claim is satisfied. Otherwise, $R_a$ and $R_b$ have (at least) three common vertices $v_1, v_2$ and $v_3$, such that $v_1$ and $v_2$ together with part of the boundaries of $R_a$ and $R_b$ form a region $R_c$, and $v_2$ and $v_3$ together with part of the boundaries of $R_a$ and $R_b$ form another region $R_d$. Figure~\ref{fig:regions} depicts the situation. Then, $R_c$ and $R_d$ only share vertex $v_2$ and the claim is also satisfied.\\ Let $R_1$ and $R_2$ be two regions that share at most two vertices, say $v_1$ and $v_2$. If some vertex $x$ in $R_1$ is at distance at least $\left \lfloor D/2 \right\rfloor +1$ from $v_1$ and $v_2$ and at distance at least $\left \lfloor D/2 \right\rfloor$ from any other boundary vertex of $R_1$, and if some vertex $y$ in $R_2$ is at distance at least $\left \lfloor D/2 \right\rfloor+1$ from $v_1$ and $v_2$ and at distance at least $\left \lfloor D/2 \right\rfloor$ from any other boundary vertex of $R_2,$ then the distance from $x$ to $y$ would be at least $D+1$, which would contradict that the diameter of $G$ is $D$. Without loss of generality, we can assume that each interior vertex of $R_1$ is at distance at most $\left \lfloor D/2 \right\rfloor$ from $v_1$ or $v_2$, or at distance at most $\left \lfloor D/2 \right\rfloor-1$ from some other boundary vertex of $R_1.$ We then give an upper bound on the maximum number $n(R_1)$ of interior vertices in $R_1$, in the same way as done in the proof of Theorem~\ref{teorema:(Delta,D)}. From each boundary vertex $x$ of $R_1$ different from $v_1$ and $v_2$, we compute the maximum possible number of vertices at distance at most $\left \lfloor D/2 \right\rfloor-1$ from $x$; for vertices $v_1$ and $v_2$ we compute the maximum possible number of vertices at distance at most $\left\lfloor D/2 \right\rfloor$. From Eqs.~(\ref{eq:stepi}) and~(\ref{eq:suma}) and the estimate~(\ref{eq:rough}) we get %$$\sum_{i=0}^{\lfloor D/2\rfloor} n_i \leq 2(\Delta-2)^{\left \lfloor D/2 \right\rfloor}$$ $$n(R_1)\leq 2\sum_{i=0}^{\lfloor D/2\rfloor} n_i + 4(2D+1)\sum_{i=0}^{\lfloor D/2\rfloor -1} n_i \leq 6(\Delta-2)^{\left \lfloor D/2 \right\rfloor}+12(2D+1)(\Delta-2)^{\left \lfloor D/2 \right\rfloor-1}.$$ We then roughly approximate, since $D\geq3$, $$ 12(2D+1)(\Delta-2)^{\left \lfloor D/2 \right\rfloor-1}<84(\Delta-2)^{\left \lfloor D/2 \right\rfloor}, $$ and we get $$ n(R_1) \leq 90(\Delta-2)^{\left \lfloor D/2 \right\rfloor}. $$ Moreover, we have that $n(R_1) \geq \frac{n+2}{9}-2(2D+1).$ Therefore, $$\frac{n+2}{9}-2(2D+1) \leq 90(\Delta-2)^{\left \lfloor D/2 \right\rfloor}$$ and $$n\leq 810(\Delta-2)^{\left \lfloor D/2 \right\rfloor}+18(2D+1)-22, \end{array} $$ which is approximately $3(\Delta-3)^k$, for $\Delta$ and $D$ sufficiently large. \item[$(c)$] For any diameter $D=2k+1$ $(k\geq 1)$ and even maximum degree $\Delta$ $(\Delta\geq10)$, there exists a maximal planar bipartite graph $G_{\Delta,D}$ whose number of vertices $n(G_{\Delta,D})$ is $$ \begin{array}{ll} n(G_{\Delta,3})=3\Delta-2 & \mbox{for } D=3, \\ n(G_{\Delta,5})=3\Delta^2 - 22\Delta + 26 & \mbox{for } D=5,\\ n(G_{\Delta,2k+1})=3\Delta^2 - 22\Delta + 26+\frac{(3\Delta-22)(\Delta-2)^2((\Delta-3)^{k-2}-1)}{(\Delta-4)} & \mbox{for } D=2k+1, \ k>2, \end{array} $$ which is approximately $3(\Delta-3)^k$, for $\Delta$ and $D$ sufficiently large. \end{itemize} \end{theorem} \begin{proof} \begin{itemize} \item[$(a)$] We present the construction for the case of even diameter $D=2k$. It is based on the one depicted in Figure~\ref{fig:arbre-esferic-Delta=4}; from a given root vertex we build an almost maximal planar bipartite graph adding the maximum number of vertices at distance $i$ from the root in step $i$ (for $0 \leq i \leq D/2$). We draw this graph on a sphere, with the root placed on the north pole and the vertices at distance $D/2$ from the root are placed on the equator, see Figure~\ref{fig:arbre-esferic3D}. Then we add a copy of this graph on the lower hemisphere, with the root on the south pole, and such that the vertices at distance $D/2$ from the south pole are identified with those already placed on the equator. %The resulting graph $G_{\Delta,D}$ is planar, as can be seen from Steinitz's Theorem~\cite{St22}, which states that a graph $G$ is the $1$-skeleton of a convex polyhedron if and only if $G$ is a simple planar graph which is 3-connected. Note that $G_{\Delta,D}$ contains vertices of degree $2$, which are some of those drawn on the equator of the sphere, but by adding auxiliary edges connecting consecutive vertices on the equator, a $3$-connected graph is obtained. Hence, $G_{\Delta,D}$ plus these additional edges form the $1$-skeleton of a convex polyhedron. It can easily be verified that $G_{\Delta,D}$ has diameter $D$: Each vertex has distances $D/2+i$ and $D/2-i$, for some $i \in \{ 0,\ldots, D/2\}$, to the vertices placed at north pole and south pole, respectively. Then, any two vertices are connected through a path of length at most $D$ that goes through one of the two poles. To count the number of vertices of $G_{\Delta,D}$, we use the formula for the number $n_i$ of vertices at distance $i$ from the root (Eq.~(\ref{eq:stepi})), calculated in the proof of Theorem~\ref{teorema:(Delta,D)}. Then, the number of vertices of $G_{\Delta,D}$ is $$ n(G_{\Delta,D})=2\sum_{i=0}^{ D/2} n_i-n_{D/2}. $$ From Eqs.~(\ref{eq:stepi}) and (\ref{eq:suma}), we obtain the claimed number of vertices of $G_{\Delta,D}$. From this expression, we get that $n(G_{\Delta,D})$ is approximately $(\Delta-2)^{k}$, for $\Delta$ and $D$ sufficiently large. \begin{figure}[t] \vskip-.75cm \begin{center} \includegraphics[width=10cm]{arbre-esferic3D.pdf} \end{center} \vskip-10.5cm \caption{The superior half of a maximal planar bipartite graph drawn on a sphere for $\Delta=4$} \label{fig:arbre-esferic3D} \end{figure} \item[$(b)$] We now consider the case of odd diameter $D=2k+1$. We give an iterative construction, which can also be used when $D=2k$, but in that case it gives a worse bound than the one given above. We construct a planar drawing of a graph $G_{\Delta,2k+3}$ with diameter $D=2k+3$ from a planar drawing of a graph $G_{\Delta,2k+1}$ with diameter $D=2k+1.$ A $\Delta$-{\it{diamond}} is a planar drawing of the complete bipartite graph $K_{2,\Delta}.$ We say that a vertex of a diamond is \emph{external} if it belongs to its outer face, and a vertex of a diamond is \emph{internal} if it is not external. A $\Delta$-diamond has four external vertices and $\Delta-2$ internal vertices. In the iterative construction, we substitute each internal vertex of a diamond by a new diamond, as shown in Figure~\ref{fig:Substitution} (middle) and (right). We use the term {\it{substitution}} to denote both this operation and the resulting subgraph. The construction is explained first for odd values of $\Delta$ (for even values of $\Delta$ it is very similar). %Let us start with the first case $k=1$. \begin{itemize} \item[$\bullet$] {$D=3$ and $\Delta$ odd $(\Delta\ge 3)$}.\\ %In this case we also allow $\Delta \in \{3,5,7\}.$ In this particular case, we consider $\Delta\geq3$, and not only $\Delta\geq9$. For $\Delta=3$, a maximal graph $G_{3,3}$ is the cube, that is the one in Figure~\ref{fig:Triangle} without the dotted lines. For $\Delta>3$ odd and $D=3$, we substitute each of the dotted lines of Figure~\ref{fig:Triangle} by a $\frac{\Delta-3}{2}$-diamond, that is, by a $K_{2,\frac{\Delta-3}{2}}$, hence obtaining a graph $G_{\Delta,3}$ with $$ n(G_{\Delta,3})=8+6\left(\frac{\Delta-3}{2}\right)=3\Delta-1 $$ vertices, which is the bound given in Theorem ~\ref{teorema:principal}. Note that this construction is also depicted in Figure~\ref{fig:3Delta-1} for $\Delta=3$ and $\Delta=5$. To prove that the graph $G_{\Delta,3}$ has diameter $D=3$, observe that for any two dotted edges of Figure~\ref{fig:Triangle}, call them $e_1$ and $e_2$, each endpoint of $e_1$ is at distance at most one to at least one endpoint of $e_2$. Hence the distance between vertices of degree two of $G_{\Delta,3}$ is at most $3$. As all the edges of the cube are present in $G_{\Delta,3}$, the other distances in this graph are also at most 3. \begin{figure}[t] \vskip-.75cm \begin{center} \includegraphics[width=12cm]{Triangle2.pdf} \end{center} \vskip-11.5cm \caption{The first step of the iterative construction.} \label{fig:Triangle} \end{figure} \item[$\bullet$] {$D=5$ and $\Delta$ odd $(\Delta\ge 9)$.}\\ We now explain the iterative construction and count the number of vertices of the graphs $G_{\Delta,D}$ obtained. In order to get a graph $G_{\Delta,5}$ with diameter $D=5$% for $\Delta \geq 9$ odd , we perform the substitution depicted in Figure~\ref{fig:Substitution} once; that is, each of the six $\frac{\Delta-3}{2}$-diamonds (which come from the dotted edges of Figure~\ref{fig:Triangle}) is replaced by the subgraph shown on the right of Figure~\ref{fig:Substitution}. From each $\frac{\Delta-3}{2}$-diamond, we obtain $(\frac{\Delta-3}{2}-2)$ new $(\Delta-1)$-diamonds, adding $2(\frac{\Delta-3}{2}-2)+1$ external vertices together with $(\frac{\Delta-3}{2}-2)(\Delta-3)$ new internal vertices. Thus the number of vertices of the graph $G_{\Delta,5}$ is $$ n(G_{\Delta,5})=8+3(\Delta-3)+6(\Delta-7)+6+3(\Delta-7)(\Delta-3)=3\Delta^2-21\Delta+26. $$ \item[$\bullet$] {$D=7$ and $\Delta$ odd $(\Delta\ge 9)$.}\\ From the graph $G_{\Delta,5}$, we perform the substitution to the $(\Delta-1)$-diamonds, whose number is $6(\frac{\Delta-3}{2}-2)$, and we obtain $6(\frac{\Delta-7}{2})(\Delta-3)$ new $(\Delta-1)$-diamonds, hence we add $3(\Delta-7)(2(\Delta-3)+1)$ external vertices and $3(\Delta-7)(\Delta-3)^2$ internal vertices, obtaining a graph with $6(\Delta-7)(\Delta-3)+3(\Delta-7)+3(\Delta-7)(\Delta-3)^2$ more vertices. Then, the number of vertices of the graph $G_{\Delta,7}$ is \begin{align*} n(G_{\Delta,7})=& \, 8+3(\Delta-3)+6+3(\Delta-7)(\Delta-1)+6(\Delta-7)(\Delta-3)+3(\Delta-7)\\ & +3(\Delta-7)(\Delta-3)^2\\ =& \, 3\Delta^3 - 30\Delta^2 + 75\Delta - 58. \end{align*} %$$14+3(\Delta-3)+3(\Delta-7)\Delta+6(\Delta-7)(\Delta-3)+3(\Delta-7)(\Delta-3)^2.$$ \item[$\bullet$] {$D=2k+1$ $(k>3)$ and $\Delta$ odd $(\Delta\ge 9)$.}\\ In general, after obtaining the graph $G_{\Delta,2k+1}$ from the graph $G_{\Delta,2k-1}$, note that $G_{\Delta,2k+1}$ has $3(\Delta-7)(\Delta-3)^{k-2}$ new diamonds, hence it has $(2(\Delta-3)+1)3(\Delta-7)(\Delta-3)^{k-3}$ new external vertices and $3(\Delta-7)(\Delta-3)^{k-1}$ new internal vertices. Then, $$n(G_{\Delta,2k+1})=n(G_{\Delta,2k-1})+3(\Delta-7)(\Delta-3)^{k-1}\left(1+\frac{2(\Delta-3)+1}{(\Delta-3)^{2}}\right).$$ Therefore, for $\Delta \geq 9$ and $D\ge 7$, the number of vertices in $G_{\Delta,D}$ is \begin{eqnarray*} n(G_{\Delta,2k+1}) &=& 5+3\Delta+3(\Delta-7)(\Delta-1) \\ && +\displaystyle\sum_{3\le i\le k}3(\Delta-7)(\Delta-3)^{i-1}\left(1+\frac{2(\Delta-3)+1}{(\Delta-3)^{2}}\right) \\ &=& 3\Delta^2 - 21\Delta + 26+\frac{3(\Delta-7)(\Delta-2)^2((\Delta-3)^{k-2}-1)}{(\Delta-4)}. \end{eqnarray*} From this expression, we get that $n(G_{\Delta,D})$ is approximately $3(\Delta-3)^k$, for $\Delta$ and $D$ sufficiently large. \end{itemize} \begin{figure}[t] \vskip-.75cm \begin{center} \includegraphics[width=14cm]{substitucio.pdf} \end{center} \vskip-5.5cm \caption{Substitution of an $r$-diamond. The inductive step.}\label{fig:Substitution} \end{figure} \item[$(c)$] $D=2k+1$ and $\Delta$ even $(\Delta \geq 10)$.\\ In the case for $\Delta $ even, the only difference from $(b)$ is that, in the first step of the construction (that is, $D=3$), we substitute one of the dotted lines of each dotted triangle by a $\frac{\Delta-2}{2}$-diamond and the other two by a $\frac{\Delta-4}{2}$-diamond. In this case we obtain the values \begin{eqnarray*} n(G_{\Delta,3}) &=& 3\Delta-2, \\ n(G_{\Delta,5}) &=& 3\Delta-2+2(\Delta-6)+2+4(\Delta-8)+4+(\Delta-6)(\Delta-3)\\ && +2(\Delta-8)(\Delta-3)= 3\Delta^2 - 22\Delta+ 26,\\ n(G_{\Delta,2k+1}) &=& 4+3\Delta+(3(\Delta-7)-1)(\Delta-1)\\ \end{eqnarray*} \begin{eqnarray*} &+& \displaystyle\sum_{3\le i\le k}(3(\Delta-7)-1)(\Delta-3)^{i-1}\left(1+\frac{2(\Delta-3)+1}{(\Delta-3)^{2}}\right)\\ &=& 3\Delta^2 - 22\Delta+ 26+\frac{(3(\Delta-7)-1)(\Delta-2)^2((\Delta-3)^{k-2}-1)}{(\Delta-4)}. \end{eqnarray*} From this expression, we get that $n(G_{\Delta,D})$ is approximately $3(\Delta-3)^k$, for $\Delta$ and $D$ sufficiently large. It remains to prove that the graphs $G_{\Delta,2k+1}$ have diameter $2k+1$. We proceed by induction on $k$. The base of induction, $k=1$, was already shown in the case $D=3$. For the inductive step, we show that the diameter of the graph $G_{\Delta,2k+3}$ obtained by substitution is at most the same as $G_{\Delta,2k+1}$ plus two units. Let $z$ and $u$ be two vertices of $G_{\Delta,2k+3}.$ If $z$ and $u$ both lie within the same substitution, then their distance is at most $4$; see Figure ~\ref{fig:Substitution} (right). Then, assume that $z$ and $u$ are not from the same substitution. It is sufficient to show that each of $z$ and $u$ is at distance at most $1$ from some vertex of $G_{\Delta,2k+3}$ that also belongs to the previous graph $G_{\Delta,2k+1}.$ This is so because all edges of $G_{\Delta,2k+1}$, but the ones replaced by a substitution, are present in $G_{\Delta,2k+3}.$ We can assume that $z$ is an interior vertex of a substitution. Let $x$ and $y$ be the two external vertices of the substitution, that are indicated in Figure~\ref{fig:Substitution} (right). Either one of the distances from $z$ to $x$ or from $z$ to $y$ is $1$, or the distances from $z$ to $x$ and from $z$ to $y$ are both $2$. In the first case, we add one step to the path connecting $x$ to $u$ or $y$ to $u$, as wanted. In the latter case, we can assign $z$ to the interior vertex $w$ of $G_{\Delta,2k+1}$ which has been replaced by a diamond, and $z$ is at distance $1$ to $w'$ and $w''$, both corresponding to vertex $w$ before the substitution (see again Figure~\ref{fig:Substitution}). In other words, in this case we can use two steps instead of one, to reach an external vertex ($x$ or $y$) of the substitution. The same argumentation applies to $u$, which completes the proof of the induction step. \end{itemize} \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% c o n c l u s i o n s %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\section{Conclusions} %In this paper, we solve the $(\Delta,2)$ and $(\Delta,3)$ problems for maximal planar bipartite graphs, and we give upper and lower bounds on the number of vertices for the $(\Delta,D)$ problem. We think these bounds could be improved with the techniques used by Tishchenko~\cite{Ti12}, but this remains for a future research. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% b i b l i o g r a f i a %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{thebibliography}{10} \bibitem{ApHa77} K. Appel, and W. Haken. \newblock The solution of the four-color map problem. \newblock \emph{Sci. Amer.} 237:108--121, 1977. \bibitem{ChEsVa07} V. Chepoi, B. Estellon, and Y. Vax\`{e}s. \newblock On covering planar graphs with a fixed number of balls. \newblock \emph{Discrete Comput. Geom.} 37:237--244, 2007. \bibitem{FeHeSe95} M. Fellows, P. Hell, and K. Seyffarth. \newblock Large planar graphs with given diameter and maximum degree. \newblock \emph{Discrete Appl. Math.} 61:133--153, 1995. \bibitem{FeHeSe98} M. Fellows, P. Hell, and K. Seyffarth. \newblock Constructions of large planar networks with given degree and diameter. \newblock \emph{Networks} 32:275--281, 1998. \bibitem{FPPV13} R. Feria-Puron, and G. Pineda-Villavicencio. \newblock Constructions of large graphs on surfaces. \newblock \emph{Graph. Combinator.} 30:895--908, 2014. \bibitem{GaPeRaSo01} C. Gavoille, D. Peleg, A. Raspaud, and E. Sopena. \newblock Small k-dominating sets in planar graphs with applications. \newblock 27th International Workshop on Graph-Theoretic Concepts in Computer Science 2001, \emph{Lect. Notes Comput. Sc.} 2204:201--216, Springer-Verlag, Berlin, 2001. \bibitem{LiTa79} R.J. Lipton, and R.E. Tarjan. \newblock A separator theorem for planar graphs. \newblock \emph{SIAM J. Appl. Math.} 36:177--189, 1979. \bibitem{LoPRPV13} E. Loz, H. P\'{e}rez-Ros\'{e}s, and G. Pineda-Villavicencio. \newblock The degree/diameter problem for planar graphs. \newblock \verb"http://combinatoricswiki.org/wiki/The_Degree_" \verb"Diameter_Problem_for_Planar_Graphs". \bibitem{HeSe93} P. Hell, and K. Seyffarth. \newblock Largest planar graphs of diameter two and fixed maximum degree. \newblock \emph{Discrete Math.} 111:313--322, 1993. \bibitem{MiSi13} M. Miller, and J. \v{S}ir\'{a}\v{n}. \newblock Moore graphs and beyond: A survey of the degree/diameter problem. \newblock \emph{Electron. J. Combin.} 20(2): \#DS14v2, 2013. \bibitem{NePiWo13} E. Nevo, G. Pineda-Villavicencio, and D.R. Wood. \newblock On the maximum order of graphs embedded in surfaces. \newblock \emph{J. Combin. Theory Ser. B}, 2015. \texttt{doi:10.1016/j.jctb.2015.12.004} \bibitem{PiWo13} G. Pineda-Villavicencio, and D.R. Wood. \newblock The degree-diameter problem for sparse graph classes. \newblock \emph{Electron. J. Combin.} 22(2): \#P2.46, 2015. %\newblock \arxiv{1307.4456}. \bibitem{Ri93} G. Ringel. \newblock Two trees in maximal planar bipartite graphs. \newblock \emph{J. Graph Theory} 17:755--758, 1993. \bibitem{RoSaSeTh96} N. Robertson, D.P. Sanders, P.D. Seymour, and R. Thomas. \newblock A new proof of the four colour theorem. \newblock \emph{Electron. Res. Announc. Amer. Math. Soc.} 2:17--25, 1996. \bibitem{SeFl96} R. Sedgewick, and P. Flajolet. \newblock \emph{An introduction to the analysis of algorithms}. \newblock Addison-Wesley, Reading, MA, 1996. \bibitem{Se89} K. Seyffarth. \newblock Maximal planar graphs of diameter two. \newblock \emph{J. Graph Theory} 13:619--648, 1989. %\bibitem{St22} %E. Steinitz. %\newblock ``Polyeder und Raumeinteilungen''. %\newblock \emph{Encyclop\"{a}die der mathematischen Wissenschaften}, 3 (Geometrie):1--139, 1922. \bibitem{Ti12} S.A. Tishchenko. \newblock Maximum size of a planar graph with given degree and even diameter. \newblock \emph{Eur. J. Combin.} 33:380--396, 2012. \bibitem{Ti12a} S.A. Tishchenko. \newblock $N$-separators in planar graphs. \newblock \emph{Eur. J. Combin.} 33:397--407, 2012. \bibitem{YaliDa02} Y. Yang, J. Lin, and Y. Dai. \newblock Largest planar graphs and largest maximal planar graphs of diameter two. \newblock \emph{J. Comput. Appl. Math.} 144:349--358, 2002. \end{thebibliography} \end{document}