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

MaRDI QIDQ521397zbMATHFDO

Authors Veit Wiechert

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

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

tree-widthgraph layoutsqueue layouts

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 $kgeq1$, 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$.

Recommendations

• Layout of Graphs with Bounded Tree-Width
• Tree-partitions of \(k\)-trees with applications in graph layout.
• Queue layouts of planar 3-trees
• Queue layouts of planar 3-trees
• Laying Out Graphs Using Queues

Cites work

• scientific article; zbMATH DE number 3917707 (Why is no real title available?)
• scientific article; zbMATH DE number 1241845 (Why is no real title available?)
• scientific article; zbMATH DE number 1944139 (Why is no real title available?)
• scientific article; zbMATH DE number 1954397 (Why is no real title available?)
• scientific article; zbMATH DE number 2159644 (Why is no real title available?)
• Bounded-degree graphs have arbitrarily large queue-number
• Characterisations and examples of graph classes with bounded expansion
• Comparing Queues and Stacks As Machines for Laying Out Graphs
• Computing straight-line 3D grid drawings of graphs in linear volume
• Embedding planar graphs in four pages
• Graph Drawing
• Graph layouts via layered separators
• Layered separators in minor-closed graph classes with applications
• Laying Out Graphs Using Queues
• Layout of Graphs with Bounded Tree-Width
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• On the Queue Number of Planar Graphs
• Queue layouts of hypercubes
• Stacks, queues and tracks: layouts of graph subdivisions
• Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions
• The Maximum Number of Edges in a Three-Dimensional Grid-Drawing
• The book thickness of a graph
• The pagenumber of \(k\)-trees is \(O(k)\)
• Three-dimensional graph drawing
• Tree-partitions of infinite graphs
• Upward three-dimensional grid drawings of graphs

Cited in

(22)

• Lazy Queue Layouts of Posets
• An improved upper bound on the queue number of planar graphs
• Bounded-degree graphs have arbitrarily large queue-number
• On mixed linear layouts of series-parallel graphs
• Queue layouts of planar 3-trees
• Queue layouts of planar 3-trees
• Planar graphs of bounded degree have bounded queue number
• The Local Queue Number of Graphs with Bounded Treewidth
• On Mixed Linear Layouts of Series-Parallel Graphs
• Layout of Graphs with Bounded Tree-Width
• Mixed linear layouts of planar graphs
• The queue-number of posets of bounded width or height
• On the queue-number of partial orders
• Linear layouts of bipartite planar graphs
• Tree-partitions of \(k\)-trees with applications in graph layout.
• On the queue number of planar graphs
• Parameterized algorithms for queue layouts
• Parameterized Algorithms for Queue Layouts
• Shallow Minors, Graph Products, and Beyond-Planar Graphs
• On the Queue Number of Planar Graphs
• The mixed page number of graphs
• Lazy queue layouts of posets

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)