1. On the number of upward planar orientations of maximal planar graphs
- Author
-
Fabrizio Frati, Joachim Gudmundsson, Emo Welzl, Frati, Fabrizio, Gudmundsson, Joachim, Welzl, Emo, and Kun-Mao Chao and Tsan-sheng Hsu and Der-Tsai Lee
- Subjects
Combinatorics ,Physics ,symbols.namesake ,Book embedding ,Planar ,General Computer Science ,Planar straight-line graph ,symbols ,Directed graph ,Computer Science::Computational Geometry ,Theoretical Computer Science ,Mathematics ,Planar graph - Abstract
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 @W^@?(1.189^n) and at most O^@?(4^n) upward planar orientations. Moreover, we show that there exist n-vertex maximal planar graphs having O^@?(2^n) upward planar orientations and n-vertex maximal planar graphs having @W^@?(2.599^n) upward planar orientations. Further, we present bounds for the maximum and the minimum number of acyclic orientations a maximal planar graph can have.
- Published
- 2014