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.


Published in:
Siam Journal On Computing, 42, 6, 2243-2285
Year:
2013
Publisher:
Philadelphia, Siam Publications
ISSN:
0097-5397
Keywords:
Laboratories:




 Record created 2014-02-17, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)