Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. On The Queue Number Of Planar Graphs
 
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.

  • Details
  • Metrics
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
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés