Level Planarity: Transitivity vs. Even Crossings

Recently, Fulek et al. [1, 2, 3] have presented Hanani-Tutte results for (radial) level planarity, i.e., a graph is (radial) level planar if it admits a (radial) level drawing where any two (independent) edges cross an even number of times. We show that the 2-Sat formulation of level planarity testing due to Randerath et al. [4] is equivalent to the strong Hanani-Tutte theorem for level planarity [3]. Further, we show that this relationship carries over to radial level planarity, which yields a novel polynomial-time algorithm for testing radial level planarity.