2018/08/29 by Guido Brückner, Ignaz Rutter, Brückner, Guido +3
Computer Science · #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.1808.09931
Appears in the Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD 2018)
arxiv created 2018/08/29 · arxiv updated 2018/08/30
Recently, Fulek et al. 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. is equivalent to the strong Hanani-Tutte theorem for level planarity. Further, we show that this relationship carries over to radial level planarity, which yields a novel polynomial-time algorithm for testing radial level planarity.