On the number of upward planar orientations of maximal planar graphs

We consider the problem of determining the maximum and the minimum number of upward planar orientations a maximal planar graph can have. We show that every n  -vertex maximal planar graph has at least Ω⁎(1.189n)Ω⁎(1.189n) and at most O⁎(4n)O⁎(4n) upward planar orientations. Moreover, we show that there exist n  -vertex maximal planar graphs having O⁎(2n)O⁎(2n) upward planar orientations and n  -vertex maximal planar graphs having Ω⁎(2.599n)Ω⁎(2.599n) upward planar orientations. Further, we present bounds for the maximum and the minimum number of acyclic orientations a maximal planar graph can have.