In the mathematical field of graph theory, the queue number of a graph is a graph invariant defined analogously to stack number (book thickness) using first-in first-out (queue) orderings in place of last-in first-out (stack) orderings.
In the mathematical field of graph theory, the queue number of a graph is a graph invariant defined analogously to stack number (book thickness) using first-in first-out (queue) orderings in place of last-in first-out (stack) orderings.
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 ab and cd are two edges in the same queue, then it should not be possible to have a < c < d < b in the vertex ordering. The queue number qn(G) of a graph G is the minimum number of queues in a queue layout. [1]
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. [1] 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. [2]
Queue layouts were defined by 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. [1]
Every tree has queue number 1, with a vertex ordering given by a breadth-first traversal. [3] Pseudoforests and grid graphs also have queue number 1. [4] 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. [5] Series–parallel graphs have queue number at most 3, [6] while the queue number of planar 3-trees is at most 5. [7]
Binary de Bruijn graphs have queue number 2. [8] The d-dimensional hypercube graph has queue number at most . [9] The queue numbers of complete graphs Kn and complete bipartite graphs Ka,b are known exactly: they are and respectively. [10]
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. [11] In 1992, Heath, Leighton & Rosenberg (1992) conjectured that every planar graph has bounded queue number. This conjecture was resolved positively in 2019 by Dujmović et al. (2020) who showed that planar graphs and, more generally, every proper minor-closed class of graphs has bounded queue number. In particular, Dujmović et al. (2020) proved that the queue number of planar graphs is at most 49, a bound which was reduced to 42 by 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. [12]
Graphs with low queue number are sparse graphs: 1-queue graphs with n vertices have at most 2n – 3 edges, [13] and more generally graphs with queue number q have at most 2qn – q(2q + 1) edges. [14] This implies that these graphs also have small chromatic number: in particular 1-queue graphs are 3-colorable, and graphs with queue number q may need at least 2q + 1 and at most 4q colors. [14] In the other direction, a bound on the number of edges implies a much weaker bound on the queue number: graphs with n vertices and m edges have queue number at most . [15] This bound is close to tight, because for random d-regular graphs the queue number is, with high probability,
Must every graph with bounded queue number also have bounded book thickness, and vice versa?
Graphs with queue number 1 have book thickness at most 2. [17] 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. [18] The book thickness may be much larger than the queue number: ternary Hamming graphs have logarithmic queue number but polynomially-large book thickness [18] and there are graphs with queue number 4 that have arbitrarily large book thickness. [17] 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. [19]
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. [20]
It is NP-complete to determine the queue number of a given graph, or even to test whether this number is 1. [21]
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 k-rainbow, a set of k edges each two of which form a nested pair. A partition of edges into queues can be performed by assigning an edge e that is the outer edge of an i-rainbow (and of no larger rainbow) to the ith queue. It is possible to construct an optimal layout in time O(m log(log n)), where n denotes the number of vertices of the input graph and m denotes the number of edges. [22]
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. [23] 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. [24]
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 X has bounded queue number if and only if for every n-vertex graph G in X, it is possible to place the vertices of G in a three-dimensional grid of dimensions O(n) × O(1) × O(1) so that no two edges (when drawn straight) cross each other. [25] 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. [26] [27] [28]
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.
In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges, vertices and by contracting edges.
In mathematics, a universal graph is an infinite graph that contains every finite graph as an induced subgraph. A universal graph of this type was first constructed by Richard Rado and is now called the Rado graph or random graph. More recent work has focused on universal graphs for a graph family F: that is, an infinite graph belonging to F that contains all finite graphs in F. For instance, the Henson graphs are universal in this sense for the i-clique-free graphs.
In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a sparse graph. The distinction of what constitutes a dense or sparse graph is ill-defined, and is often represented by 'roughly equal to' statements. Due to this, the way that density is defined often depends on the context of the problem.
In graph theory, Schnyder's theorem is a characterization of planar graphs in terms of the order dimension of their incidence posets. It is named after Walter Schnyder, who published its proof in 1989.
In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings in a book, a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie on this boundary line, called the spine, and the edges are required to stay within a single half-plane. The book thickness of a graph is the smallest possible number of half-planes for any book embedding of the graph. Book thickness is also called pagenumber, stacknumber or fixed outerthickness. Book embeddings have also been used to define several other graph invariants including the pagewidth and book crossing number.
In graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph, and the pathwidth of G is a number that measures how much the path was thickened to form G. More formally, a path-decomposition is a sequence of subsets of vertices of G such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as interval thickness, vertex separation number, or node searching number.
In graph theory, the strong product is a way of combining two graphs to make a larger graph. Two vertices are adjacent in the strong product when they come from pairs of vertices in the factor graphs that are either adjacent or identical. The strong product is one of several different graph product operations that have been studied in graph theory. The strong product of any two graphs can be constructed as the union of two other products of the same two graphs, the Cartesian product of graphs and the tensor product of graphs.
Planarity is a 2005 puzzle computer game by John Tantalo, based on a concept by Mary Radcliffe at Western Michigan University. The name comes from the concept of planar graphs in graph theory; these are graphs that can be embedded in the Euclidean plane so that no edges intersect. By Fáry's theorem, if a graph is planar, it can be drawn without crossings so that all of its edges are straight line segments. In the planarity game, the player is presented with a circular layout of a planar graph, with all the vertices placed on a single circle and with many crossings. The goal for the player is to eliminate all of the crossings and construct a straight-line embedding of the graph by moving the vertices one by one into better positions.
In the mathematical field of graph theory, a star coloring of a graph G is a (proper) vertex coloring in which every path on four vertices uses at least three distinct colors. Equivalently, in a star coloring, the induced subgraphs formed by the vertices of any two colors has connected components that are star graphs. Star coloring has been introduced by Grünbaum (1973). The star chromatic number of G is the fewest colors needed to star color G.
In the study of graph algorithms, an implicit graph representation is a graph whose vertices or edges are not represented as explicit objects in a computer's memory, but rather are determined algorithmically from some other input, for example a computable function.
In graph theory, the tree-depth of a connected undirected graph is a numerical invariant of , the minimum height of a Trémaux tree for a supergraph of . This invariant and its close relatives have gone under many different names in the literature, including vertex ranking number, ordered chromatic number, and minimum elimination tree height; it is also closely related to the cycle rank of directed graphs and the star height of regular languages. Intuitively, where the treewidth of a graph measures how far it is from being a tree, this parameter measures how far a graph is from being a star.
In graph theory, a k-tree is an undirected graph formed by starting with a (k + 1)-vertex complete graph and then repeatedly adding vertices in such a way that each added vertex v has exactly k neighbors U such that, together, the k + 1 vertices formed by v and U form a clique.
In combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles. Apollonian networks may equivalently be defined as the planar 3-trees, the maximal planar chordal graphs, the uniquely 4-colorable planar graphs, and the graphs of stacked polytopes. They are named after Apollonius of Perga, who studied a related circle-packing construction.
In graph drawing and geometric graph theory, the slope number of a graph is the minimum possible number of distinct slopes of edges in a drawing of the graph in which vertices are represented as points in the Euclidean plane and edges are represented as line segments that do not pass through any non-incident vertex.
In topological graph theory, a 1-planar graph is a graph that can be drawn in the Euclidean plane in such a way that each edge has at most one crossing point, where it crosses a single additional edge. If a 1-planar graph, one of the most natural generalizations of planar graphs, is drawn that way, the drawing is called a 1-plane graph or 1-planar embedding of the graph.
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 Plotkin, Rao & Smith (1994), who attributed their invention to Charles E. Leiserson and Sivan Toledo.
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, is equivalent to the existence of separator theorems for these families. Families with these properties have efficient algorithms for problems including the subgraph isomorphism problem and model checking for the first order theory of graphs.
David Ronald Wood is a Professor in the School of Mathematics at Monash University in Melbourne, Australia. His research area is discrete mathematics and theoretical computer science, especially structural graph theory, extremal graph theory, geometric graph theory, graph colouring, graph drawing, and combinatorial geometry.
The twin-width of an undirected graph is a natural number associated with the graph, used to study the parameterized complexity of graph algorithms. Intuitively, it measures how similar the graph is to a cograph, a type of graph that can be reduced to a single vertex by repeatedly merging together twins, vertices that have the same neighbors. The twin-width is defined from a sequence of repeated mergers where the vertices are not required to be twins, but have nearly equal sets of neighbors.
