Results 1 to 10 of about 9,663,355 (323)
Bounded-Degree Graphs have Arbitrarily Large Queue-Number [PDF]
Discrete Mathematics & Theoretical Computer Science, 2008 It is proved that there exist graphs of bounded degree with arbitrarily large queue-number. In particular, for all Δ ≥ 3 and for all sufficiently large n, there is a simple Δ-regular n-vertex graph with queue-number at least c √ Δ n 1/2-1/Δ for ...
David R. Wood
doaj +8 more sources
Stack number and queue number of graphs [PDF]
arXiv.org, 2023 In this paper we give an overview of the graph invariants queue number and stack number (the latter also called the page number or book thickness). Due to their similarity, it has been studied for a long time, whether one of them is bounded in terms of the other. It is now known that the stack number is not bounded by the queue number.
Adam Straka
semanticscholar +5 more sources
On the Queue-Number of Graphs with Bounded Tree-Width [PDF]
The Electronic Journal of Combinatorics, 2017 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\geq0$, graphs with tree-width at most $k$ have queue-number at most $2^k-
Veit Wiechert
semanticscholar +5 more sources
The Queue-Number of Posets of Bounded Width or Height [PDF]
International Symposium Graph Drawing and Network Visualization, 2018 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.
Kolja Knauer +2 more
semanticscholar +9 more sources
Stack-Number is Not Bounded by Queue-Number [PDF]
Combinatorica, 2021 We describe a family of graphs with queue-number at most 4 but unbounded stack-number. This resolves open problems of Heath, Leighton and Rosenberg (1992) and Blankenship and Oporowski (1999).
Dujmović, Vida +4 more
openaire +3 more sources
On the Queue Number of Planar Graphs [PDF]
International Symposium Graph Drawing and Network Visualization, 2021 A k-queue layout is a special type of a linear layout, in which the linear order avoids (k+1)-rainbows, i.e., k+1 independent edges that pairwise form a nested pair. The optimization goal is to determine the queue number of a graph, i.e., the minimum value of k for which a k-queue layout is feasible. Recently, Dujmovi et al. [J.
Michael A. Bekos +2 more
semanticscholar +4 more sources
Planar Graphs have Bounded Queue-Number [PDF]
2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), 2019 We show that planar graphs have bounded queue-number, thus proving a conjecture of Heath et al. [66] from 1992. The key to the proof is a new structural tool called layered partitions , and the result that every planar graph has a vertex-partition and a layering, such that each part has a bounded number of vertices ...
Dujmović, Vida V. +5 more
openaire +9 more sources
On the Queue-Number of Partial Orders [PDF]
International Symposium Graph Drawing and Network Visualization, 2021 Appears in the Proceedings of the 29th International Symposium on Graph Drawing and Network Visualization (GD 2021)
Felsner, Stefan +2 more
openaire +4 more sources
On the Queue Number of Planar Graphs [PDF]
2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 2013 We prove that planar graphs have poly-logarithmic queue number, thus improving upon the previous polynomial upper bound. Consequently, planar graphs admit 3D straight-line crossing-free grid drawings in small volume.
Giuseppe Di Battista +2 more
openalex +5 more sources
Discrete Mathematics & Theoretical Computer Science, 2004 A \emph(k,t)-track layout of a graph G consists of a (proper) vertex t-colouring of G, a total order of each vertex colour class, and a (non-proper) edge k-colouring such that between each pair of colour classes no two monochromatic edges cross.
Vida Dujmović +2 more
doaj +7 more sources