Results 1 to 10 of about 9,676,374 (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 +9 more sources
An Improved Upper Bound on the Queue Number of Planar Graphs [PDF]
Algorithmica, 2022 A k -queue layout is a special type of a linear layout, in which the linear order avoids $$(k+1)$$ ( k + 1 ) -rainbows, that is, $$k+1$$ k + 1 independent edges that pairwise form a nested pair. The optimization goal is to determine the queue number of a
Michael A. Bekos +2 more
semanticscholar +4 more sources
On the Queue Number of Planar Graphs [PDF]
2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 2010 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
semanticscholar +6 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.
Michael A. Bekos +2 more
semanticscholar +6 more sources
On the Queue-Number of Partial Orders [PDF]
International Symposium Graph Drawing and Network Visualization, 2021 The queue-number of a poset is the queue-number of its cover graph viewed as a directed acyclic graph, i.e., when the vertex order must be a linear extension of the poset.
Stefan Felsner +2 more
semanticscholar +6 more sources
Track Drawings of Graphs with Constant Queue Number [PDF]
International Symposium Graph Drawing and Network Visualization, 2004 A k-track drawing is a crossing-free 3D straight-line drawing of a graph G on a set of k parallel lines called tracks. The minimum value of k for which G admits a k-track drawing is called the track number of G. In [9] it is proved that every graph from a proper minor closed family has constant track number if and only if it has constant queue number ...
Emilio Di Giacomo, Henk Meijer
semanticscholar +6 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 ...
Adam Straka
semanticscholar +3 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, Leighton and Rosenberg 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 ...
V. Dujmović +5 more
semanticscholar +9 more sources
Stack-Number is Not Bounded by Queue-Number [PDF]
Combinatorica, 2020 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).
Vida Dujmovi'c +4 more
semanticscholar +3 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