  In this paper we settle the computational complexity of two open problems
related to the extension of the notion of level planarity to surfaces different
from the plane. Namely, we show that the problems of testing the existence of a
level embedding of a level graph on the surface of the rolling cylinder or on
the surface of the torus, respectively known by the name of $\textit{Cyclic
Level Planarity}$ and $\textit{Torus Level Planarity}$, are polynomial-time
solvable.
  Moreover, we show a complexity dichotomy for testing the
$\textit{Simultaneous Level Planarity}$ of a set of level graphs, with respect
to both the number of level graphs and the number of levels.
