Abstract
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.
Details
Title
On The Queue Number Of Planar Graphs
Author(s)
Di Battista, Giuseppe ; Frati, Fabrizio ; Pach, Janos
Published in
Siam Journal On Computing
Pagination
43
Volume
42
Issue
6
Pages
2243-2285
Date
2013
Publisher
Philadelphia, Siam Publications
ISSN
0097-5397
Keywords
Other identifier(s)
View record in Web of Science
Laboratories
DCG
Record Appears in
Scientific production and competences > SB - School of Basic Sciences > SB Archives > DCG - Chair of Combinatorial Geometry
Scientific production and competences > SB - School of Basic Sciences > Mathematics
Peer-reviewed publications
Work produced at EPFL
Journal Articles
Published
Scientific production and competences > SB - School of Basic Sciences > Mathematics
Peer-reviewed publications
Work produced at EPFL
Journal Articles
Published
Record creation date
2014-02-17