• DocumentCode
    1708583
  • 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
  • fYear
    2010
  • Firstpage
    365
  • Lastpage
    374
  • 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;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on
  • Conference_Location
    Las Vegas, NV
  • ISSN
    0272-5428
  • Print_ISBN
    978-1-4244-8525-3
  • Type

    conf

  • DOI
    10.1109/FOCS.2010.42
  • Filename
    5671214
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1708583