REAL

On the queue number of planar graphs

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)

[img]
Preview
Text
10.1.1.190.1097.pdf

Download (758kB) | Preview

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 Edit Item