Level-planarity: transitivity vs. even crossings (Q2094894)

Summary: \textit{R. Fulek} et al. [in: Thirty essays on geometric graph theory. Berlin: Springer. 263--287 (2013; Zbl 1272.05129); Lect. Notes Comput. Sci. 9801, 468--481 (2016; Zbl 1478.68237)] 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 \textit{B. Randerath} et al. [Electron. Notes Discrete Math. 9, no pag. (2001; Zbl 0990.90530)] is equivalent to the strong Hanani-Tutte theorem for level-planarity. 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..