Di Battista, Giuseppe and Frati, Fabrizio and Pach, János (2013) On the queue number of planar graphs. SIAM JOURNAL ON COMPUTING, 42 (6). pp. 2243-2285. ISSN 0097-5397 (print); 1095-7111 (online)
|
Text
10.1.1.190.1097.pdf Download (758kB) | Preview |
Official URL: http://doi.org/10.1137/130908051
Abstract
We prove that planar graphs have O(log2 n) queue number, thus improving upon the previous O(Formula Presented) 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. © 2013 Society for Industrial and Applied Mathematics.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | graph layout, queue number, planar graph |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika > QA166-QA166.245 Graphs theory / gráfelmélet |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 22 Nov 2019 08:25 |
| Last Modified: | 22 Nov 2019 08:25 |
| URI: | http://real.mtak.hu/id/eprint/103561 |
Actions (login required)
 |
Edit Item |
