The queue-number of posets of bounded width or height

DOI10.1007/978-3-030-04414-5_14MaRDI QIDQ1725753zbMATH OpenOpenAlexFDO

Authors Kolja Knauer, Piotr Micek, Torsten Ueckerdt

Publication date 15 February 2019

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

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Combinatorics of partially ordered sets (06A07)

Abstract: Heath and Pemmaraju conjectured that the queue-number of a poset is bounded by its width and if the poset is planar then also by its height. We show that there are planar posets whose queue-number is larger than their height, refuting the second conjecture. On the other hand, we show that any poset of width $2$ has queue-number at most $2$, thus confirming the first conjecture in the first non-trivial case. Moreover, we improve the previously best known bounds and show that planar posets of width $w$ have queue-number at most $3w-2$ while any planar poset with $0$ and $1$ has queue-number at most its width.

Recommendations

• Stack and Queue Layouts of Posets
• Queue layouts of two-dimensional posets
• Lazy Queue Layouts of Posets
• Lazy queue layouts of posets
• On the queue-number of the hypercube
• On the queue-number of graphs with bounded tree-width
• Wide posets with fixed height and cutset number
• Upper bounds on the queue number of \(k\)-ary \(n\)-cubes
• On the queue number of planar graphs
• On the Queue Number of Planar Graphs

Cites work

• scientific article; zbMATH DE number 2159655 (Why is no real title available?)
• A decomposition theorem for partially ordered sets
• Bipartite graphs, upward drawings, and planarity
• Characterisations and examples of graph classes with bounded expansion
• Comparing Queues and Stacks As Machines for Laying Out Graphs
• Intransitive indifference with unequal indifference intervals
• Laying Out Graphs Using Queues
• N-free posets as generalizations of series-parallel posets
• Partial orders of dimension 2
• Stack and Queue Layouts of Posets
• Stacks, queues and tracks: layouts of graph subdivisions
• The queue-number of posets of bounded width or height

Cited in

(5)

• The queue-number of posets of bounded width or height
• Lazy queue layouts of posets
• On the queue-number of partial orders
• Lazy Queue Layouts of Posets
• Queue layouts of two-dimensional posets

This page was built for publication: The queue-number of posets of bounded width or height

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