The maximum genus of graphs with diameter three (Q1297478)

The maximum genus \(\gamma_M(G)\) of the graph \(G\) is the largest integer \(g\) such that \(G\) has a cellular embedding in the orientable surface of genus \(g\). It follows from the Euler-Poincaré equation that \(\gamma_M(G)\leq \lfloor\beta(G)/2\rfloor\) where \(\beta(G)\) is the Betti number, or cycle rank, of \(G\), and the graph \(G\) is said to be up-embeddable if equality holds. The authors show that if \(G\) is a simple graph with diameter three then \(G\) is up-embeddable unless \(G\) belongs to one of two well-understood families of graphs whose maximum genus equals \((\beta(G)- 2)/2\).