
In the
mathematical
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
field of
graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, the queue number of a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discret ...
is a
graph invariant
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
* Graph (topology), a topological space resembling a graph in the sense of discre ...
defined analogously to
stack number (book thickness) using
first-in first-out (queue) orderings in place of
last-in first-out (stack) orderings.
Definition
A queue layout of a given graph is defined by a
total ordering
In mathematics, a total order or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( re ...
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 and are two edges in the same queue, then it should not be possible to have in the vertex ordering. The queue number of a graph is the minimum number of queues in a queue layout.
[.]
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
A cylinder () has traditionally been a three-dimensional solid, one of the most basic of curvilinear geometric shapes. In elementary geometry, it is considered a prism with a circle as its base.
A cylinder may also be defined as an infinite ...
, 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.
Queue layouts were defined by , by analogy to previous work on
book embedding
In graph theory, a book embedding is a generalization of planar graph, planar embedding of a Graph (discrete mathematics), graph to embeddings in a ''book'', a collection of half-planes all having the same Line (geometry), line as their boundary ...
s 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
permutation
In mathematics, a permutation of a set can mean one of two different things:
* an arrangement of its members in a sequence or linear order, or
* the act or process of changing the linear order of an ordered set.
An example of the first mean ...
s using systems of parallel queues, and may be motivated by applications in
VLSI design and in communications management for
distributed algorithm A distributed algorithm is an algorithm designed to run on computer hardware constructed from interconnected processors. Distributed algorithms are used in different application areas of distributed computing, such as telecommunications, scientifi ...
s.
Graph classes with bounded queue number
Every
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only ...
has queue number 1, with a vertex ordering given by a
breadth-first traversal.
Pseudoforest
In graph theory, a pseudoforest is an undirected graphThe kind of undirected graph considered here is often called a multigraph or pseudograph, to distinguish it from a simple graph. in which every Connected component (graph theory), connected com ...
s and
grid graph
In graph theory, a lattice graph, mesh graph, or grid graph is a Graph (discrete mathematics), graph whose graph drawing, drawing, Embedding, embedded in some Euclidean space , forms a regular tiling. This implies that the group (mathematics), g ...
s also have queue number 1.
Outerplanar graph
In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.
Outerplanar graphs may be characterized (analogously to Wagner's theorem for planar graphs) by the two f ...
s 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.
Series–parallel graph
In graph theory, series–parallel graphs are graphs with two distinguished vertices called ''terminals'', formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits.
Definition and t ...
s have queue number at most 3, while
the queue number of planar 3-trees is at most 5.
Binary
de Bruijn graph
In graph theory, an -dimensional De Bruijn graph of symbols is a directed graph representing overlaps between sequences of symbols. It has vertices, consisting of all possible sequences of the given symbols; the same symbol may appear multiple ...
s have queue number 2. The ''d''-dimensional
hypercube graph
In graph theory, the hypercube graph is the graph formed from the vertices and edges of an -dimensional hypercube. For instance, the cubical graph, cube graph is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube.
has ...
has queue number at most
. The queue numbers of
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices i ...
s ''K''
''n'' and
complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17.
Graph theory ...
s ''K''
''a'',''b'' are known exactly: they are
and
respectively.
Every 1-queue graph is a
planar graph
In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...
, 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. In 1992, conjectured that every planar graph has bounded queue number. This conjecture was resolved positively in 2019 by who showed that planar graphs and, more generally, every proper minor-closed class of graphs has bounded queue number. In particular, proved that the queue number of planar graphs is at most 49, a bound which was reduced to 42 by .
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.
Related invariants
Graphs with low queue number are
sparse graph
In mathematics, a dense graph is a Graph (discrete mathematics), graph in which the number of edges is close to the maximal number of edges (where every pair of Vertex (graph theory), vertices is connected by one edge). The opposite, a graph with ...
s: 1-queue graphs with vertices have at most edges, and more generally graphs with queue number have at most edges.
[.] This implies that these graphs also have small
chromatic number
In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...
: in particular 1-queue graphs are 3-colorable, and graphs with queue number may need at least and at most colors.
In the other direction, a bound on the number of edges implies a much weaker bound on the queue number: graphs with vertices and edges have queue number at most . This bound is close to tight, because for random -regular graphs the queue number is, with high probability,
:
Graphs with queue number 1 have book thickness at most 2.
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.
[.]
The book thickness may be much larger than the queue number: ternary
Hamming graph
Hamming graphs are a special class of graphs named after Richard Hamming and used in several branches of mathematics (graph theory) and computer science. Let be a set of elements and a positive integer. The Hamming graph has vertex set , ...
s have logarithmic queue number but polynomially-large book thickness
and there are graphs with queue number 4 that have arbitrarily large book thickness.
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 graph
In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...
s with 3-page book embeddings have bounded queue number, then all graphs with bounded book thickness have bounded queue number.
[.]
asked whether the queue number of a graph could be bounded as a function of its
treewidth
In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests
...
, 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.
Computational complexity
It is
NP-complete
In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''.
Somewhat more precisely, a problem is NP-complete when:
# It is a decision problem, meaning that for any ...
to determine the queue number of a given graph, or even to test whether this number is 1.
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, a set of edges each two of which form a nested pair. A partition of edges into queues can be performed by assigning an edge that is the outer edge of an -rainbow (and of no larger rainbow) to the th queue. It is possible to construct an optimal layout in time , where denotes the number of vertices of the input graph and denotes the number of edges.
Graphs of bounded queue number also have
bounded expansion
In graph theory, a family of graphs is said to have bounded expansion if all of its shallow minors are sparse graphs. Many natural families of sparse graphs have bounded expansion. A closely related but stronger property, polynomial expansion, i ...
, meaning that their
shallow minor
In graph theory, a shallow minor or limited-depth minor is a restricted form of a graph minor in which the subgraphs that are contracted to form the minor have small diameter. Shallow minors were introduced by , who attributed their invention to ...
s are
sparse graph
In mathematics, a dense graph is a Graph (discrete mathematics), graph in which the number of edges is close to the maximal number of edges (where every pair of Vertex (graph theory), vertices is connected by one edge). The opposite, a graph with ...
s with a ratio of edges to vertices (or equivalently
degeneracy or
arboricity
The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning forests needed to cover all the edges of the graph. The Nash-Williams theorem provid ...
) 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 The term subgraph can refer to:
*The security-focused Linux-based Subgraph operating system, see Subgraph (operating system)
*Subgraph of a function, see Hypograph (mathematics)
*In graph theory
In mathematics and computer science, graph theo ...
for pattern graphs of bounded size have
linear time
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations ...
algorithms for these graphs. More generally, because of their bounded expansion, it is possible to check whether any sentence in the
first-order logic
First-order logic, also called predicate logic, predicate calculus, or quantificational logic, is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over ...
of graphs is valid for a given graph of bounded queue number, in linear time.
Application in graph drawing
Although queue layouts do not necessarily produce good two-dimensional
graph drawing
Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graph (discrete mathematics), graphs arising from applications such ...
s, they have been used for three-dimensional graph drawing. In particular, a graph class has bounded queue number if and only if for every -vertex graph in , it is possible to place the vertices of in a three-dimensional grid of dimensions so that no two edges (when drawn straight) cross each other. Thus, for instance,
de Bruijn graph
In graph theory, an -dimensional De Bruijn graph of symbols is a directed graph representing overlaps between sequences of symbols. It has vertices, consisting of all possible sequences of the given symbols; the same symbol may appear multiple ...
s, graphs of bounded treewidth,
planar graph
In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...
s, and proper
minor-closed graph families have three-dimensional embeddings of linear volume.
Notes
References
*.
*.
*.
*.
*.
*.
*.
*
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
{{refend
External links
Stack and Queue Layouts Problems presented in Summer 2009, Research Experiences for Graduate Students, Douglas B. West
Topological graph theory
Graph invariants
NP-complete problems