We prove that planar graphs have polylogarithmic queue number, thus improving upon the previous polynomial upper bound. Consequently, planar graphs admit 3D straight-line crossing-free grid drawings in small volume.
DI BATTISTA, G., Frati, F., Pach, J. (2010). On the Queue Number of Planar Graphs. In 51st Annual IEEE Symposium on Foundations of Computer Science (pp.365-374). IEEE Computer Society [10.1007/978-3-642-13739-6_12].
On the Queue Number of Planar Graphs
DI BATTISTA, Giuseppe;FRATI, FABRIZIO;
2010-01-01
Abstract
We prove that planar graphs have polylogarithmic queue number, thus improving upon the previous polynomial upper bound. Consequently, planar graphs admit 3D straight-line crossing-free grid drawings in small volume.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
