Planarity Variants for Directed Graphs
Guido Brückner · Repository KITopen (Karlsruhe Institute of Technology) · 2021
Level-Planarity: Transitivity vs. Even CrossingsRecently, Fulek et al. [FPS17,FPS16,FPSŠ13] 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. [Ran+01] is equivalent to the strong Hanani-Tutte theorem for level-planarity [FPSŠ13].Further, we show that this relationship carries over to radial level planarity, which yields a novel polynomial-time algorithm for testing radial level-planarity in the spirit of Randerath et al.