On the queue-number of graphs with bounded tree-width

Publication date 10 April 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.06091, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p65

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

graph layouts queue layouts tree-width

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12)

Abstract: 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 g e q 1

, graphs with tree-width at most

k

have queue-number at most

2^{k} - 1

. This improves upon double exponential upper bounds due to Dujmovi'c et al. and Giacomo et al. 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 Rengarajan and Veni Madhavan, namely, that the maximal queue-number of

2

-trees is equal to

3

.

Review text

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.

Recommendations

Cites work

Cited in

(27)

This page was built for publication: On the queue-number of graphs with bounded tree-width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q521397)