In order to attack some problems in computational geometry, Hoffmann and Kriegel [ SIAM J. Discrete Math., 9 (1996), pp. 210--224] considered the problem of whether a plane map can be extended to a 3-colorable triangulation by adding edges. In this paper, we improve their results to maps on nonspherical surfaces, by showing the following two results for a mosaic, that is, a map on a surface each of whose faces is triangular or quadrangular: a necessary and sufficient condition for mosaics on a surface to be extended to a 3-colorable triangulation (Theorem 5) and an explicit formula for calculating the number of distinct 3-colorable triangulations extended from a given mosaic on a surface (Theorem 6). These results suggest a significant gap between the planar case and the nonspherical case. We also show that they improve several known results and have an application to a polychromatic coloring.

For a positive integer $k$, a book (with $k$ pages) is a topological space consisting of a spine, which is a line, and $k$ pages, which are half-planes with the spine as their boundary. We say that a graph $G$ admits a $k$-page book embedding or is $k$-page book embeddable if there exists a linear ordering of the vertices on the spine and one can assign the edges of $G$ to $k$ pages such that no two edges of the same page cross. Yannakakis proved that every plane graph admits a 4-page book embedding. In this paper, we improve this to graphs on the projective plane, that is, those embedded on the projective plane without edge-crossings. Nakamoto and Nozawa showed that every graph on the projective plane admits a 9-page book embedding. In this paper, we improve the latter result to 6-page embedding. Furthermore, we also prove that every graph on the projective plane admits a 3-page book embedding if it is 5-connected and a 5-page book embedding if it is 4-connected. Our idea of the proofs is to use a Tutte path, which is different from previous ones.

Extension of a graph $G$ is the construction of a new graph with certain properties by adding edges to some pairs of vertices in $G$. In this paper, we focus on extension of a quadrangulation of a surface to even triangulations, where a quadrangulation is a map on a surface with every face quadrangular and a triangulation is even if all the vertices have even degree. Zhang and He [SIAM J. Comput., 34 (2005), pp. 683--696] gave a formula for the exact number of distinct even triangulations extended from a given plane quadrangulation, and a lower bound of the number for the case of orientable nonspherical surfaces. They also posed the problem of finding the exact number for the latter case. In this paper, using topological methods, we improve the results by Zhang and He in the following directions: (I) extension of quadrangulations of a nonorientable surface and (II) complete enumeration of even triangulations extended from a given quadrangulation of a nonspherical surface. Indeed, we completely solve the problem by Zhang and He.

Endo proved that every toroidal graph has a book embedding with at most seven pages. In this paper, we prove that every toroidal bipartite graph has a book embedding with at most five pages. In order to do so, we prove that every bipartite torus quadrangulation Q with n vertices admits two disjoint noncontractible simple closed curves cutting the torus into two annuli so that each of the two annuli contains a spanning connected subgraph of Q with exactly n edges satisfying a certain condition.

A Möbius triangulation is a triangulation on the Möbius band. A geometric realization of a map M on a surface $\Sigma$ is an embedding of $\Sigma$ into a Euclidean 3-space $\mathbb{R}^3$ such that each face of M is a flat polygon. In this paper, we shall prove that every 5-connected triangulation on the Möbius band has a geometric realization. In order to prove it, we prove that if G is a 5-connected triangulation on the projective plane, then for any face f of G, the Möbius triangulation $G-f$ obtained from G by removing the interior of f has a geometric realization.

In this paper, we shall characterize triangulations on the Klein bottle without $K_6$-minors. Our characterization implies that every 5-connected triangulation on the Klein bottle has a $K_6$-minor. The connectivity “5" is best possible in a sense that there is a 4-connected triangulation on the Klein bottle without $K_6$-minors.