We provide a new linear-time algorithm for determining the vertex-connectivity of graphs with bounded genus. This generalizes and streamlines a linear-time algorithm for graphs with bounded crossing number which was recently obtained by Biedl, Bose and Murali [ESA 2024]. Compared to applying the even more recent fixed parameter linear-time algorithm for deciding bounded vertex-connectivity announced by Korhonen [STOC 2025] to graphs of bounded genus,our algorithm is far simpler, its correctness easier to establish, and it makes use of geometric ideas, as is natural for surface-embedded graphs.

A drawing of a graph is 1-planar if each edge participates in at most one crossing and adjacent edges do not cross. Up to symmetry, each crossing in a 1-planar drawing belongs to one out of six possible crossing types, where a type characterizes the subgraph induced by the four vertices of the crossing edges. Each of the 63 possible nonempty subsets S of crossing types gives a recognition problem: does a given graph admit an S-restricted drawing, that is, a 1-planar drawing where the crossing type of each crossing is in S? We show that there is a set Sbad with three crossing types and the following properties: If S contains no crossing type from Sbad, then the recognition of graphs that admit an S-restricted drawing is fixed-parameter tractable with respect to the treewidth of the input graph. If S contains any crossing type from Sbad, then it is NP-hard to decide whether a graph has an S-restricted drawing, even when considering graphs of constant pathwidth. We also extend this characterization of crossing types to 1-planar straight-line drawings and show the same complexity behaviour parameterized by treewidth.

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.

The minor crossing number of a graph G is defined as the minimum crossing number of all graphs that contain G as a minor. Basic properties of this new invariant are presented. We study topological structure of graphs with bounded minor crossing number and obtain a new strong version of a lower bound based on the genus. We also give a generalization of an inequality of Moreno and Salazar crossing numbers of a graph and its minors.