On the queue-number of graphs with bounded tree-width (Q521397)

Summary: A queue layout of a graph consists of a linear order on the vertices and an assignment of the edges to queues, such that no two edges in a single queue are nested.~The minimum number of queues needed in a queue layout of a graph is called its queue-number. We show that for each \(k\geq 0\), graphs with tree-width at most \(k\) have queue-number at most \(2^k-1\). This improves upon double exponential upper bounds due to \textit{V. Dujmović} et al. [SIAM J. Comput. 34, No. 3, 553--579 (2005; Zbl 1069.05055)] and \textit{E. Di Giacomo} et al. [Comput. Geom. 32, No. 1, 26--58 (2005; Zbl 1101.68066)]. As a consequence we obtain that these graphs have track-number at most \(2^{O(k^2)}\). We complement these results by a construction of \(k\)-trees that have queue-number at least \(k+1\). Already in the case \(k=2\) this is an improvement to existing results and solves a problem of \textit{S. Rengarajan} and \textit{C. E. Veni Madhavan} [``Stack and queue number of 2-trees'', Lect. Notes Comput. Sci. 959, 203--212 (1995; \url{doi:10.1007/BFb0030834})], namely, that the maximal queue-number of 2-trees is equal to 3.