queue number

A queue layout of a given graph is defined by a total ordering of the vertices of the graph together with a partition of the edges into a number of "queues". The set of edges in each queue is required to avoid edges that are properly nested: if {{mvar|ab}} and {{mvar|cd}} are two edges in the same queue, then it should not be possible to have {{math|a < c < d < b}} in the vertex ordering. The queue number {{math|qn(G)}} of a graph {{mvar|G}} is the minimum number of queues in a queue layout.{{harvtxt|Heath|Rosenberg|1992}}.

Equivalently, from a queue layout, one could process the edges in a single queue using a queue data structure, by considering the vertices in their given ordering, and when reaching a vertex, dequeueing all edges for which it is the second endpoint followed by enqueueing all edges for which it is the first endpoint. The nesting condition ensures that, when a vertex is reached, all of the edges for which it is the second endpoint are ready to be dequeued. Another equivalent definition of queue layouts involves embeddings of the given graph onto a cylinder, with the vertices placed on a line in the cylinder and with each edge wrapping once around the cylinder. Edges that are assigned to the same queue are not allowed to cross each other, but crossings are allowed between edges that belong to different queues.{{harvtxt|Auer|Bachmaier|Brandenburg|Brunner|2011}}.

Queue layouts were defined by {{harvtxt|Heath|Rosenberg|1992}}, by analogy to previous work on book embeddings of graphs, which can be defined in the same way using stacks in place of queues. As they observed, these layouts are also related to earlier work on sorting permutations using systems of parallel queues, and may be motivated by applications in VLSI design and in communications management for distributed algorithms.

Every tree has queue number 1, with a vertex ordering given by a breadth-first traversal.{{harvtxt|Heath|Rosenberg|1992}}, Proposition 4.1. Pseudoforests and grid graphs also have queue number 1.{{harvtxt|Heath|Rosenberg|1992}}, Propositions 4.2 and 4.3. Outerplanar graphs have queue number at most 2; the 3-sun graph (a triangle with each of its edges replaced by a triangle) is an example of an outerplanar graph whose queue number is exactly 2.{{harvtxt|Heath|Leighton|Rosenberg|1992}}; {{harvtxt|Rengarajan|Veni Madhavan|1995}}. Series–parallel graphs have queue number at most 3,{{harvtxt|Rengarajan|Veni Madhavan|1995}}. while

the queue number of planar 3-trees is at most 5.{{harvtxt|Alam|Bekos|Gronemann|Kaufmann|Pupyrev|2020}}.

Binary de Bruijn graphs have queue number 2.{{harvtxt|Heath|Rosenberg|1992}}, Proposition 4.6. The d-dimensional hypercube graph has queue number at most $d-\backslash lfloor\backslash log\_2\; d\backslash rfloor$.{{harvtxt|Gregor|Škrekovski|Vukašinović|2012}} The queue numbers of complete graphs K_n and complete bipartite graphs K_a,b are known exactly: they are $\backslash lfloor\; n/2\backslash rfloor$ and $\backslash min\backslash \{\backslash lceil\; a/2\backslash rceil,\backslash lceil\; b/2\backslash rceil\backslash \}$

respectively.{{harvtxt|Heath|Rosenberg|1992}}, Propositions 4.7 and 4.8.

Every 1-queue graph is a planar graph, with an "arched leveled" planar embedding in which the vertices are placed on parallel lines (levels) and each edge either connects vertices on two consecutive levels or forms an arch that connects two vertices on the same level by looping around all previous levels. Conversely, every arched leveled planar graph has a 1-queue layout.{{harvtxt|Heath|Rosenberg|1992}}, Theorem 3.2. In 1992, {{harvtxt|Heath|Leighton|Rosenberg|1992}} conjectured that every planar graph has bounded queue number. This conjecture was resolved positively in 2019 by {{harvtxt|Dujmović|Joret|Micek|Morin|2020}} who showed that planar graphs and, more generally, every proper minor-closed class of graphs has bounded queue number. In particular, {{harvtxt|Dujmović|Joret|Micek|Morin|2020}} proved that the queue number of planar graphs is at most 49, a bound which was reduced to 42 by {{harvtxt|Bekos|Gronemann|Raftopoulou|2021}}.

Using a variation of queue number called the strong queue number, the queue number of a graph product can be bounded by a function of the queue numbers and strong queue numbers of the factors in the product.{{harvtxt|Wood|2005}}.

Graphs with low queue number are sparse graphs: 1-queue graphs with {{mvar|n}} vertices have at most {{math|2n – 3}} edges,{{harvtxt|Heath|Rosenberg|1992}}, Theorem 3.6 and more generally graphs with queue number {{mvar|q}} have at most {{math|2qn – q(2q + 1)}} edges.{{harvtxt|Dujmović|Wood|2004}}. This implies that these graphs also have small chromatic number: in particular 1-queue graphs are 3-colorable, and graphs with queue number {{mvar|q}} may need at least {{math|2q + 1}} and at most {{math|4q}} colors. In the other direction, a bound on the number of edges implies a much weaker bound on the queue number: graphs with {{mvar|n}} vertices and {{mvar|m}} edges have queue number at most {{tmath|O(\sqrt{m})}}.{{harvtxt|Heath|Leighton|Rosenberg|1992}}. A polynomial-time algorithm for finding a layout with close to this many queues is given by {{harvtxt|Shahrokhi|Shi|2000}}. {{harvtxt|Dujmović|Wood|2004}} improved the constant factor in this bound to {{tmath|e\sqrt{m} }}, where {{math|e}}is the base of the natural logarithm. This bound is close to tight, because for random {{mvar|d}}-regular graphs the queue number is, with high probability,

:$\backslash Omega\backslash left(\backslash frac\{\backslash sqrt\{dn\}\}\{n^\{1/d\}\}\backslash right).${{harvtxt|Heath|Leighton|Rosenberg|1992}}; {{harvtxt|Wood|2008}}.

{{unsolved|mathematics|Must every graph with bounded book thickness also have bounded queue-number?}}

Graphs with queue number 1 have book thickness at most 2.{{harvtxt|Dujmović|Eppstein|Hickingbotham|Morin|Wood|2022}}

For any fixed vertex ordering, the product of the book thickness and queue numbers for that ordering is at least as large as the cutwidth of the graph divided by its maximum degree.{{harvtxt|Heath|Leighton|Rosenberg|1992}}.

The book thickness may be much larger than the queue number: ternary Hamming graphs have logarithmic queue number but polynomially-large book thickness and there are graphs with queue number 4 that have arbitrarily large book thickness. {{harvtxt|Heath|Leighton|Rosenberg|1992}} conjectured that the queue number is at most a linear function of the book thickness, but no functional bound in this direction is known. It is known that, if all bipartite graphs with 3-page book embeddings have bounded queue number, then all graphs with bounded book thickness have bounded queue number.{{harvtxt|Dujmović|Wood|2005}}.

{{harvtxt|Ganley|Heath|2001}} asked whether the queue number of a graph could be bounded as a function of its treewidth, and cited an unpublished Ph.D. dissertation of S. V. Pemmaraju as providing evidence that the answer was no: planar 3-trees appeared from this evidence to have unbounded queue number. However, the queue number was subsequently shown to be bounded by a (doubly exponential) function of the treewidth.{{harvtxt|Dujmović|Wood|2003}}; {{harvtxt|Dujmović|Morin|Wood|2005}}. See {{harvtxt|Wood|2002}} for a weaker preliminary result, bounding the queue number by the pathwidth or by a combination of treewidth and degree.

It is NP-complete to determine the queue number of a given graph, or even to test whether this number is 1.{{harvtxt|Heath|Rosenberg|1992}}, Corollary 3.9.

However, if the vertex ordering of a queue layout is given as part of the input,

then the optimal number of queues for the layout equals the maximum number of edges in a Rainbow coloring, a set of {{mvar|k}} edges each two of which form a nested pair. A partition of edges into queues can be performed by assigning an edge {{mvar|e}} that is the outer edge of an {{mvar|i}}-rainbow (and of no larger rainbow) to the {{mvar|i}}th queue. It is possible to construct an optimal layout in time {{math|O(m log(log n))}}, where {{mvar|n}} denotes the number of vertices of the input graph and {{mvar|m}} denotes the number of edges.{{harvtxt|Heath|Rosenberg|1992}}, Theorem 2.3.

Graphs of bounded queue number also have bounded expansion, meaning that their shallow minors are sparse graphs with a ratio of edges to vertices (or equivalently degeneracy or arboricity) that is bounded by a function of the queue number and the depth of the minor. As a consequence, several algorithmic problems including subgraph isomorphism for pattern graphs of bounded size have linear time algorithms for these graphs.{{harvtxt|Nešetřil|Ossona de Mendez|Wood|2012}}; {{harvtxt|Nešetřil|Ossona de Mendez|2012}}, pp. 321–327. More generally, because of their bounded expansion, it is possible to check whether any sentence in the first-order logic of graphs is valid for a given graph of bounded queue number, in linear time.{{harvtxt|Nešetřil|Ossona de Mendez|2012}}, Theorem 18.2, p. 401.

Although queue layouts do not necessarily produce good two-dimensional graph drawings, they have been used for three-dimensional graph drawing. In particular, a graph class {{mvar|X}} has bounded queue number if and only if for every {{mvar|n}}-vertex graph {{mvar|G}} in {{mvar|X}}, it is possible to place the vertices of {{mvar|G}} in a three-dimensional grid of dimensions {{math|O(n) × O(1) × O(1)}} so that no two edges (when drawn straight) cross each other.{{harvtxt|Wood|2002}}; {{harvtxt|Dujmović|Pór|Wood|2004}}; {{harvtxt|Dujmović|Morin|Wood|2005}}. See {{harvtxt|Di Giacomo|Meijer|2004}} for tighter bounds on the grid dimensions for graphs of small queue number. Thus, for instance, de Bruijn graphs, graphs of bounded treewidth, planar graphs, and proper minor-closed graph families have three-dimensional embeddings of linear volume.{{harvtxt|Dujmović|Wood|2003}}{{harvtxt|Dujmović|Morin|Wood|2005}}{{harvtxt|Dujmović|Joret|Micek|Morin|2020}}

{{reflist|30em}}

{{refbegin|30em}}

• {{citation

| last1 = Auer | first1 = Christopher

| last2 = Bachmaier | first2 = Christian

| last3 = Brandenburg | first3 = Franz Josef

| last4 = Brunner | first4 = Wolfgang

| last5 = Gleißner | first5 = Andreas

| contribution = Plane drawings of queue and deque graphs

| doi = 10.1007/978-3-642-18469-7_7

| location = Heidelberg

| mr = 2781254

| pages = 68–79

| publisher = Springer

| series = Lecture Notes in Computer Science

| title = Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21–24, 2010, Revised Selected Papers

| volume = 6502

| isbn = 978-3-642-18468-0

| year = 2011| doi-access = free

}}.

• {{citation

| last1 = Alam | first1 = Jawaherul Md.

| last2 = Bekos | first2 = Michael A.

| last3 = Gronemann | first3 = Martin

| last4 = Kaufmann | first4 = Michael

| last5 = Pupyrev | first5 = Sergey

| doi = 10.1007/s00453-020-00697-4

| issue = 82

| volume = 9

| journal = Algorithmica

| title = Queue Layouts of Planar 3-Trees

| year = 2020

| pages = 2564–2585

| arxiv = 1808.10841| s2cid = 52143414

}}.

• {{citation

| last1 = Bekos | first1 = Michael A.

| last2 = Gronemann | first2 = Martin

| last3 = Raftopoulou | first3 = Chrysanthi N.

| contribution = On the Queue Number of Planar Graphs

| location = Heidelberg

| publisher = Springer

| series = Lecture Notes in Computer Science

| title = Graph Drawing: 29th International Symposium, GD 2021, Tuebingen, Germany, September 14–17, 2021, Revised Selected Papers

| year = 2021

}}.

• {{citation

| last1 = Di Battista | first1 = Giuseppe

| last2 = Frati | first2 = Fabrizio

| last3 = Pach | first3 = János | author3-link = János Pach

| doi = 10.1137/130908051

| issue = 6

| journal = SIAM Journal on Computing

| mr = 3141759

| pages = 2243–2285

| title = On the queue number of planar graphs

| volume = 42

| year = 2013| url = http://real.mtak.hu/103561/1/10.1.1.190.1097.pdf

}}.

• {{citation

| last1 = Di Giacomo | first1 = Emilio

| last2 = Meijer | first2 = Henk

| contribution = Track drawings of graphs with constant queue number

| doi = 10.1007/978-3-540-24595-7_20

| mr = 2177595

| pages = 214–225

| publisher = Springer | location = Berlin

| series = Lecture Notes in Computer Science

| title = Graph Drawing: 11th International Symposium, GD 2003 Perugia, Italy, September 21–24, 2003 Revised Papers

| volume = 2912

| isbn = 978-3-540-20831-0

| year = 2004| doi-access = free

}}.

• {{citation

| last = Dujmović | first = Vida | author-link = Vida Dujmović

| arxiv = 1302.0304

| doi = 10.1016/j.jctb.2014.07.005

| journal = Journal of Combinatorial Theory

| mr = 3279388

| pages = 79–89

| series = Series B

| title = Graph layouts via layered separators

| volume = 110

| year = 2015| s2cid = 60212 }}.

• {{citation

| last1 = Dujmović | first1 = Vida | author1-link = Vida Dujmović

| last2 = Eppstein | first2 = David | author2-link = David Eppstein

| last3 = Hickingbotham | first3 = Robert

| last4 = Morin | first4 = Pat | author4-link = Pat Morin

| last5 = Wood | first5 = David R. | author5-link = David Wood (mathematician)

| arxiv = 2011.04195

| doi = 10.1007/s00493-021-4585-7

| issue = 2

| journal = Combinatorica

| mr = 4426297

| pages = 151–164

| title = Stack-number is not bounded by queue-number

| volume = 42

| year = 2022| s2cid = 226281691 }}.

• {{citation

| last1 = Dujmović | first1 = Vida | author1-link = Vida Dujmović

| last2 = Joret | first2 = Gwenäel

| last3 = Micek | first3 = Piotr

| last4 = Morin | first4 = Pat | author4-link = Pat Morin

| last5 = Ueckerdt | first5 = Torsten

| last6 = Wood | first6 = David R. | author6-link = David Wood (mathematician)

| title = Planar graphs have bounded queue-number

| arxiv = 1904.04791

| journal = Journal of the ACM

| year = 2020| volume = 67

| issue = 4

| pages = 1–38

| doi = 10.1145/3385731

}}

• {{citation

| last1 = Dujmović | first1 = Vida | author1-link = Vida Dujmović

| last2 = Morin | first2 = Pat | author2-link = Pat Morin

| last3 = Wood | first3 = David R. | author3-link = David Wood (mathematician)

| arxiv = cs/0406024

| doi = 10.1137/S0097539702416141

| issue = 3

| journal = SIAM Journal on Computing

| mr = 2137079

| pages = 553–579

| title = Layout of graphs with bounded tree-width

| volume = 34

| year = 2005| s2cid = 3264071 }}.

• {{citation

| last1 = Dujmović | first1 = Vida | author1-link = Vida Dujmović

| last2 = Morin | first2 = Pat | author2-link = Pat Morin

| last3 = Wood | first3 = David R. | author3-link = David Wood (mathematician)

| arxiv = 1306.1595

| contribution = Layered separators for queue layouts, 3D graph drawing and nonrepetitive coloring

| doi = 10.1109/FOCS.2013.38

| title = Proceedings of the 54th IEEE Symposium on Foundations of Computer Science (FOCS '13)

| pages = 280–289

| year = 2013| isbn = 978-0-7695-5135-7 | s2cid = 5613857 }}.

• {{citation

| last1 = Dujmović | first1 = Vida | author1-link = Vida Dujmović

| last2 = Pór | first2 = Attila

| last3 = Wood | first3 = David R. | author3-link = David Wood (mathematician)

| issue = 2

| journal = Discrete Mathematics & Theoretical Computer Science

| mr = 2180055

| pages = 497–521

| title = Track layouts of graphs

| url = http://www.dmtcs.org/pdfpapers/dm060221.pdf

| volume = 6

| year = 2004| arxiv = cs/0407033

| bibcode = 2004cs........7033D

}}.

• {{citation

| last1 = Dujmović | first1 = Vida | author1-link = Vida Dujmović

| last2 = Wood | first2 = David R. | author2-link = David Wood (mathematician)

| contribution = Tree-partitions of k-trees with applications in graph layout

| doi = 10.1007/978-3-540-39890-5_18

| mr = 2080081

| pages = 205–217

| publisher = Springer | location = Berlin

| series = Lecture Notes in Computer Science

| title = Graph-theoretic Concepts in Computer Science: 29th International Workshop, WG 2003. Elspeet, The Netherlands, June 19-21, 2003. Revised Papers

| volume = 2880

| isbn = 978-3-540-20452-7 | year = 2003| citeseerx = 10.1.1.130.1914

}}.

• {{citation

| last1 = Dujmović | first1 = Vida | author1-link = Vida Dujmović

| last2 = Wood | first2 = David R. | author2-link = David Wood (mathematician)

| issue = 2

| journal = Discrete Mathematics & Theoretical Computer Science

| mr = 2081479

| pages = 339–357

| title = On linear layouts of graphs

| url = http://www.dmtcs.org/pdfpapers/dm060210.pdf

| volume = 6

| year = 2004}}.

• {{citation

| last1 = Dujmović | first1 = Vida | author1-link = Vida Dujmović

| last2 = Wood | first2 = David R. | author2-link = David Wood (mathematician)

| issue = 1

| journal = Discrete Mathematics & Theoretical Computer Science

| mr = 2164064

| pages = 155–201

| title = Stacks, queues and tracks: layouts of graph subdivisions

| url = http://dmtcs.org/pdfpapers/dm070111.pdf

| volume = 7

| year = 2005| doi = 10.46298/dmtcs.346 }}.

• {{citation

| last1 = Ganley | first1 = Joseph L.

| last2 = Heath | first2 = Lenwood S.

| doi = 10.1016/S0166-218X(00)00178-5

| issue = 3

| journal = Discrete Applied Mathematics

| mr = 1818238

| pages = 215–221

| title = The pagenumber of k-trees is O(k)

| volume = 109

| year = 2001| doi-access = free

}}.

• {{citation

| last1 = Gregor | first1 = Petr

| last2 = Škrekovski | first2 = Riste

| last3 = Vukašinović | first3 = Vida

| doi = 10.1016/j.endm.2011.09.067

| journal = Electronic Notes in Discrete Mathematics

| pages = 413–418

| title = On the queue-number of the hypercube

| volume = 38

| year = 2011}}.

• {{citation

| last1 = Gregor | first1 = Petr

| last2 = Škrekovski | first2 = Riste

| last3 = Vukašinović | first3 = Vida

| doi = 10.1137/100813865

| journal = SIAM Journal on Discrete Mathematics

| pages = 77–88

| title = Queue layouts of hypercubes

| volume = 26

| issue = 1

| year = 2012| citeseerx = 10.1.1.417.7129

}}.

• {{citation

| last1 = Hasunuma | first1 = Toru

| last2 = Hirota | first2 = Misa

| doi = 10.1016/j.ipl.2007.05.006

| issue = 2

| journal = Information Processing Letters

| mr = 2343263

| pages = 41–44

| title = An improved upper bound on the queuenumber of the hypercube

| volume = 104

| year = 2007}}.

• {{citation

| last1 = Heath | first1 = Lenwood S.

| last2 = Leighton | first2 = Frank Thomson | author2-link = F. Thomson Leighton

| last3 = Rosenberg | first3 = Arnold L. | author3-link = Arnold L. Rosenberg

| doi = 10.1137/0405031

| issue = 3

| journal = SIAM Journal on Discrete Mathematics

| mr = 1172748

| pages = 398–412

| title = Comparing queues and stacks as {{sic|mechanisms|hide=y|expected=The journal metadata has "machines" but the actual text of the article has "mechanisms".}} for laying out graphs

| volume = 5

| year = 1992}}.

• {{citation

| last1 = Heath | first1 = Lenwood S.

| last2 = Rosenberg | first2 = Arnold L. | author2-link = Arnold L. Rosenberg

| doi = 10.1137/0221055

| issue = 5

| journal = SIAM Journal on Computing

| mr = 1181408

| pages = 927–958

| title = Laying out graphs using queues

| volume = 21

| year = 1992}}.

• {{citation

| last1 = Nešetřil | first1 = Jaroslav | author1-link = Jaroslav Nešetřil

| last2 = Ossona de Mendez | first2 = Patrice | author2-link = Patrice Ossona de Mendez

| doi = 10.1007/978-3-642-27875-4

| isbn = 978-3-642-27874-7

| mr = 2920058

| publisher = Springer

| series = Algorithms and Combinatorics

| title = Sparsity: Graphs, Structures, and Algorithms

| volume = 28

| year = 2012 }}.

• {{citation

| last1 = Nešetřil | first1 = Jaroslav | author1-link = Jaroslav Nešetřil

| last2 = Ossona de Mendez | first2 = Patrice | author2-link = Patrice Ossona de Mendez

| last3 = Wood | first3 = David R. | author3-link = David Wood (mathematician)

| arxiv = 0902.3265

| doi = 10.1016/j.ejc.2011.09.008

| issue = 3

| journal = European Journal of Combinatorics

| mr = 2864421

| pages = 350–373

| title = Characterisations and examples of graph classes with bounded expansion

| volume = 33

| year = 2012| s2cid = 2633083 }}.

• {{citation

| last1 = Pai | first1 = Kung-Jui

| last2 = Chang | first2 = Jou-Ming

| last3 = Wang | first3 = Yue-Li

| doi = 10.1016/j.ipl.2008.04.019

| issue = 3

| journal = Information Processing Letters

| mr = 2452135

| pages = 107–109

| title = A note on "An improved upper bound on the queuenumber of the hypercube"

| volume = 108

| year = 2008}}.

• {{citation

| last1 = Rengarajan | first1 = S.

| last2 = Veni Madhavan | first2 = C. E.

| contribution = Stack and queue number of 2-trees

| doi = 10.1007/BFb0030834

| mr = 1450116

| pages = 203–212

| publisher = Springer | location = Berlin

| series = Lecture Notes in Computer Science

| title = Computing and Combinatorics: First Annual International Conference, COCOON '95 Xi'an, China, August 24–26, 1995, Proceedings

| volume = 959

| isbn = 978-3-540-60216-3

| year = 1995}}.

• {{citation

| last1 = Shahrokhi | first1 = Farhad

| last2 = Shi | first2 = Weiping

| doi = 10.1006/jagm.1999.1049

| issue = 1

| journal = Journal of Algorithms

| mr = 1732197

| pages = 40–53

| title = On crossing sets, disjoint sets, and pagenumber

| volume = 34

| year = 2000}}.

• {{citation

| last = Wood | first = David R. | author-link = David Wood (mathematician)

| contribution = Queue layouts, tree-width, and three-dimensional graph drawing

| doi = 10.1007/3-540-36206-1_31

| mr = 2046017

| pages = 348–359

| publisher = Springer | location = Berlin

| series = Lecture Notes in Computer Science

| title = FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science, 22nd Conference Kanpur, India, December 12–14, 2002, Proceedings

| volume = 2556

| isbn = 978-3-540-00225-3 | year = 2002}}.

• {{citation

| last = Wood | first = David R. | author-link = David Wood (mathematician)

| issue = 1

| journal = Discrete Mathematics & Theoretical Computer Science

| mr = 2183176

| pages = 255–268

| title = Queue layouts of graph products and powers

| url = http://www.dmtcs.org/pdfpapers/dm070115.pdf

| volume = 7

| year = 2005| doi = 10.46298/dmtcs.352 | s2cid = 2361133 }}.

• {{citation

| last = Wood | first = David R. | author-link = David Wood (mathematician)

| arxiv = math/0601293

| journal = Discrete Mathematics & Theoretical Computer Science

| volume = 10

| issue = 1

| pages = 27–34

| title = Bounded-degree graphs have arbitrarily large queue-number

| url = http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/viewArticle/541

| year = 2008| bibcode = 2006math......1293W

}}.

{{refend}}

• [http://www.math.illinois.edu/~dwest/regs/queuenum.html Stack and Queue Layouts], Problems presented in Summer 2009, Research Experiences for Graduate Students, Douglas B. West

Category:Topological graph theory

Category:Graph invariants

Category:NP-complete problems