Back to Search
Start Over
ON THE QUEUE NUMBER OF PLANAR GRAPHS.
- Source :
-
SIAM Journal on Computing . 2013, Vol. 42 Issue 6, p2243-2285. 43p. - Publication Year :
- 2013
-
Abstract
- We prove that planar graphs have O(log² n) queue number, thus improving upon the previous O(√n) upper bound. Consequently, planar graphs admit three-dimensional straight-line crossing-free grid drawings in O(n log8 n) volume, thus improving upon the previous O(n3/2) upper bound. [ABSTRACT FROM AUTHOR]
- Subjects :
- *PLANAR graphs
*QUEUING theory
*GRAPH theory
*GEOMETRY
*MATHEMATICAL research
Subjects
Details
- Language :
- English
- ISSN :
- 00975397
- Volume :
- 42
- Issue :
- 6
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 93430019
- Full Text :
- https://doi.org/10.1137/130908051