On topological aspects of orientations (Q5931445)

This paper studies orientations of planar graphs with a constant indegree of the internal vertex set. A 2-orientation (3-orientation) of a planar graph is an orientation of the internal edges such that all internal vertices have indegree 2 (3). The authors show that 2-orientations of a maximal bipartite planar graph are in bijection with its separating decompositions (specific decompositions into two trees), and 3-orientations of a maximal planar graph are in bijection with its Schnyder decompositions (specific decompositions into three trees, introduced by \textit{W.~ Schnyder} in [Order 5, 323-343 (1989; Zbl 0675.06001)]). Then they relate 3-connectivity of planar graphs to properties of their 2-orientations and 4-connectivity of maximal planar graphs to properties of their 3-orientations. This yields algorithms for testing 3-connectivity of a 2-connected planar graph and 4-connectivity of a maximal planar graph in linear time.