Infoscience

Journal article

On The Queue Number Of Planar Graphs

We prove that planar graphs have O(log(2) n) queue number, thus improving upon the previous O(root n) upper bound. Consequently, planar graphs admit three-dimensional straight-line crossing-free grid drawings in O(n log(8) n) volume, thus improving upon the previous O(n(3/2)) upper bound.

Fulltext

Related material