Title :
On the Queue Number of Planar Graphs
Author :
Battista, G.D. ; Frati, Fabrizio ; Pach, János
Author_Institution :
Dipt. di Inf. e Autom., Roma Tre Univ., Rome, Italy
Abstract :
We prove that planar graphs have poly-logarithmic queue number, thus improving upon the previous polynomial upper bound. Consequently, planar graphs admit 3D straight-line crossing-free grid drawings in small volume.
Keywords :
computational complexity; computational geometry; graph theory; polynomials; queueing theory; 3D straight-line crossing-free grid drawings; planar graphs; poly-logarithmic queue number; polynomial upper bound; Books; Heating; Joining processes; Layout; Partitioning algorithms; Three dimensional displays; Upper bound; planar graphs; queue layout; straight-line drawing; volume;
Conference_Titel :
Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on
Conference_Location :
Las Vegas, NV
Print_ISBN :
978-1-4244-8525-3
DOI :
10.1109/FOCS.2010.42
