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

zbMATH Open1358.05060arXiv1608.06091MaRDI QIDQ521397FDOQ521397

Authors: Veit Wiechert 

Publication date: 10 April 2017

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

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

Full work available at URL: https://arxiv.org/abs/1608.06091

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

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

zbMATH Keywords

tree-widthgraph layoutsqueue layouts

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (22)

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

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)