Level-Planarity: Transitivity vs. Even Crossings

The strong Hanani-Tutte theorem states that a graph is planar if and only if it can be drawn such that any two edges that do not share an end cross an even number of times. Fulek et al. (2013, 2016, 2017) have presented Hanani-Tutte results for (radial) level-planarity where the $y$-coordinates (distances to the origin) of the vertices are prescribed. We show that the 2-SAT formulation of level-planarity testing due to Randerath et al. (2001) is equivalent to the strong Hanani-Tutte theorem for level-planarity (2013). By elevating this relationship to radial level planarity, we obtain a novel polynomial-time algorithm for testing radial level-planarity in the spirit of Randerath et al.