research article

On The Queue Number Of Planar Graphs

Di Battista, Giuseppe
•
Frati, Fabrizio  
•
Pach, Janos  
2013
Siam Journal On Computing

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.

Cite this item

Di Battista, G., Frati, F., & Pach, J. (2013). On The Queue Number Of Planar Graphs. Siam Journal on Computing, 42(6), 2243–2285. https://doi.org/10.1137/130908051

Click Copy to copy the citation, or select the text manually.

Type
research article
DOI
10.1137/130908051
Web of Science ID

WOS:000328889400009

Author(s)
Di Battista, Giuseppe
Frati, Fabrizio  
Pach, Janos  
Date Issued

2013

Publisher

Siam Publications

Published in
Siam Journal On Computing
Volume

42

Issue

6

Start page

2243

End page

2285

Subjects

graph layout

•

queue number

•

planar graph

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCG  
Available on Infoscience
February 17, 2014
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/100854