A dominating set of a graph G is connected if it induces a connected graph in G. For planar triangulations, it has been known since 1990 that every n-vertex triangulation admits a connected dominating set of size at most n/2 - 1, and no improvement to this bound was known for over three decades. We break this longstanding barrier by showing that every n-vertex triangulation has a connected dominating set of size at most 10n/21. Equivalently, every triangulation admits a spanning tree with at least 11n/21 leaves. Moreover, we present an algorithm that computes such a set in optimal linear time. Our result narrows the gap to the best known lower bound and has graph drawing applications, establishing a bound for one-bend free sets and improving the known bound for simultaneous planar embeddings.

Cops and Robbers is a game played on a graph where a set of cops attempt to capture a single robber. The game proceeds in rounds, where each round first consists of the cops' turn, followed by the robber’s turn. In the first round, the cops place themselves on a subset of vertices, after which the robber chooses a vertex to place himself. From the next round onwards, in the cops' turn, every cop can choose to either stay on the same vertex or move to an adjacent vertex, and likewise the robber in his turn. The robber is considered to be captured if, at any point in time, there is some cop on the same vertex as the robber. The cops win if they can capture the robber within a finite number of rounds; else the robber wins. A natural question in this game concerns the cop-number of a graph - the minimum number of cops needed to capture a robber. It has long been known that graphs embeddable (without crossings) on surfaces of bounded genus have bounded cop-number. In contrast, it was shown recently that the class of 1-planar graphs - graphs that can be drawn on the plane with at most one crossing per edge - does not have bounded cop-number. This paper initiates an investigation into how the distance between crossing pairs of edges influences a graph’s cop number. In particular, we look at Distance d Cops and Robbers, a variant of the classical game, where the robber is considered to be captured if there is a cop within distance d of the robber. Let c_d(G) denote the minimum number of cops required in the graph G to capture a robber within distance d. We look at various classes of graphs, such as 1-plane graphs, k-plane graphs (graphs where each edge is crossed at most k times), and even general graph drawings, and show that if every crossing pair of edges can be connected by a path of small length, then c_d(G) is bounded, for small values of d. For example, we show that if a graph G admits a drawing in which every pair of crossing edges is contained in a path of length at most 3, then c₄(G) ≤ 21. And if the drawing permits a stronger assumption that the endpoints of every crossing induce the complete graph K₄, then c₃(G) ≤ 9. The tools and techniques that we develop in this paper are sufficiently general, enabling us to examine graphs drawn not only on the sphere but also on orientable and non-orientable surfaces.

We show that every n-vertex planar graph is contained in the graph obtained from a fan by blowing up each vertex by a complete graph of order ). Equivalently, every n-vertex planar graph G has a set X of ) vertices such that G — X has bandwidth ). This result holds in the more general setting of graphs contained in the strong product of a bounded treewidth graph and a path, which includes bounded genus graphs, graphs excluding a fixed apex graph as a minor, and k-planar graphs for fixed k. These results are obtained using two ingredients. The first is a new local sparsification lemma, which shows that every n-vertex planar graph G has a set of O ((n log n )/D ) vertices whose removal results in a graph with local density at most D. The second is a generalization of a method of Feige and Rao, that relates bandwidth and local density using volume-preserving Euclidean embeddings.

The goal of local certification is to locally convince the vertices of a graph $G$ that $G$ satisfies a given property. A prover assigns short certificates to the vertices of the graph, then the vertices are allowed to check their certificates and the certificates of their neighbors, and based only on this local view, they must decide whether $G$ satisfies the given property. If the graph indeed satisfies the property, all vertices must accept the instance, and otherwise at least one vertex must reject the instance (for any possible assignment of certificates). The goal is to minimize the size of the certificates. In this paper we study the local certification of geometric and topological graph classes. While it is known that in $n$-vertex graphs, planarity can be certified locally with certificates of size $O(\log n)$, we show that several closely related graph classes require certificates of size $Ω(n)$. This includes penny graphs, unit-distance graphs, (induced) subgraphs of the square grid, 1-planar graphs, and unit-square graphs. These bounds are tight up to a constant factor and give the first known examples of hereditary (and even monotone) graph classes for which the certificates must have linear size. For unit-disk graphs we obtain a lower bound of $Ω(n^{1-δ})$ for any $δ>0$ on the size of the certificates, and an upper bound of $O(n \log n)$. The lower bounds are obtained by proving rigidity properties of the considered graphs, which might be of independent interest.

We prove that for every planar graph X of treedepth h, there exists a positive integer c such that for every X-minor-free graph G, there exists a graph H of treewidth at most f (h) such that G is isomorphic to a subgraph of H ⊠ Kc. This is a qualitative strengthening of the Grid-Minor Theorem of Robertson and Seymour (JCTB, 1986), and treedepth is the optimal parameter in such a result. As an example application, we use this result to improve the upper bound for weak coloring numbers of graphs excluding a given graph as a minor.

Abstract. Alon, Seymour, and Thomas [ J. Amer. Math. Soc., 3 (1990), pp. 801–808] proved that every [Formula: see text]-vertex graph excluding [Formula: see text] as a minor has treewidth less than [Formula: see text]. Illingworth, Scott, and Wood [ Product Structure of Graphs with an Excluded Minor, preprint, arXiv:2104.06627 , 2022] recently refined this result by showing that every such graph is a subgraph of some graph with treewidth [Formula: see text], where each vertex is blown up by a complete graph of order [Formula: see text]. Solving an open problem of Illingworth, Scott, and Wood [2022], we prove that the treewidth bound can be reduced to 4 while keeping blowups of order [Formula: see text]. As an extension of the Lipton–Tarjan theorem, in the case of planar graphs, we show that the treewidth can be further reduced to 2, which is best possible. We generalize this result for [Formula: see text]-minor-free graphs, with blowups of order [Formula: see text]. This setting includes graphs embeddable on any fixed surface.

Abstract. This is a corrigendum for the article “Orthogonal Tree-Decompositions of Graphs” [SIAM J. Discrete Math. 32(2):839–863, 2018].

Hadwiger’s Conjecture asserts that every $K_{h}$-minor-free graph is properly $(h-1)$-colourable. We prove the following improper analogue of Hadwiger’s Conjecture: for fixed h, every $K_{h}$-minor-free graph is $(h-1)$-colourable with monochromatic components of bounded size. The number of colours is best possible regardless of the size of monochromatic components. It solves an open problem of Edwards, Kang, Kim, Oum and Seymour [SIAM J. Disc. Math. 2015], and concludes a line of research initiated in 2007. Similarly, for fixed $t \geqslant s$, we show that every $K_{s, t}$-minor-free graph is $(s+1)$-colourable with monochromatic components of bounded size. The number of colours is best possible, solving an open problem of van den Heuvel and Wood [J. London Math. Soc. 2018]. We actually prove a single theorem from which both of the above results are immediate corollaries. For an excluded apex minor, we strengthen the result as follows: for fixed $t \geqslant s \geqslant 3$, and for any fixed apex graph X, every $K_{s, t}$-subgraph-free X-minor-free graph is $(s+1)$-colourable with monochromatic components of bounded size. The number of colours is again best possible.

We show that, if an n-vertex triangulation G of maximum degree $$\Delta $$ has a dual that contains a cycle of length $$\ell $$ , then G has a non-crossing straight-line drawing in which some set, called a collinear set, of $$\Omega (\ell /\Delta ^4)$$ vertices lie on a line. Using the current lower bounds on the length of longest cycles in cubic 3-connected graphs, this implies that every n-vertex planar graph of maximum degree $$\Delta $$ has a collinear set of size $$\Omega (n^{0.8}/\Delta ^4)$$ .

We show that there exists an adjacency labelling scheme for planar graphs where each vertex of an n -vertex planar graph G is assigned a (1 + o(1)) log 2 n -bit label and the labels of two vertices u and v are sufficient to determine if uv is an edge of G . This is optimal up to the lower order term and is the first such asymptotically optimal result. An alternative, but equivalent, interpretation of this result is that, for every positive integer n , there exists a graph U n with n 1+o(1) vertices such that every n -vertex planar graph is an induced subgraph of U n . These results generalize to a number of other graph classes, including bounded genus graphs, apex-minor-free graphs, bounded-degree graphs from minor closed families, and k -planar graphs.

We show that there exists an adjacency labelling scheme for planar graphs where each vertex of an n-vertex planar graph G is assigned a (1+o(1))log2n-bit label and the labels of two vertices u and v are sufficient to determine if uv is an edge of G. This is optimal up to the lower order term and is the first such asymptotically optimal result. An alternative, but equivalent, interpretation of this result is that, for every positive integer n, there exists a graph Un with n1+o(1)vertices such that every n-vertex planar graph is an induced subgraph of Un. These results generalize to a number of other graph classes, including bounded genus graphs, apex-minor-free graphs, bounded-degree graphs from minor closed families, and k-planar graphs.

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 in each layer, and the quotient graph has bounded treewidth. This result generalises for graphs of bounded Euler genus. Moreover, we prove that every graph in a minor-closed class has such a layered partition if and only if the class excludes some apex graph. Building on this work and using the graph minor structure theorem, we prove that every proper minor-closed class of graphs has bounded queue-number. Layered partitions have strong connections to other topics, including the following two examples. First, they can be interpreted in terms of strong products. We show that every planar graph is a subgraph of the strong product of a path with some graph of bounded treewidth. Similar statements hold for all proper minor-closed classes. Second, we give a simple proof of the result by DeVos et al. [31] that graphs in a proper minor-closed class have low treewidth colourings.

We prove that a minor-closed class of graphs has bounded layered pathwidth if and only if some apex-forest is not in the class. This generalizes a theorem of Robertson and Seymour, which says that a minor-closed class of graphs has bounded pathwidth if and only if some forest is not in the class.

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-partition and a layering, such that each part has a bounded number of vertices in each layer, and the quotient graph has bounded treewidth. This result generalises for graphs of bounded Euler genus. Moreover, we prove that every graph in a minor-closed class has such a layered partition if and only if the class excludes some apex graph. Building on this work and using the graph minor structure theorem, we prove that every proper minor-closed class of graphs has bounded queue-number. Layered partitions can be interpreted in terms of strong products. We show that every planar graph is a subgraph of the strong product of a path with some graph of bounded treewidth. Similar statements hold for all proper minor-closed classes.

We show that if a planar graph G has a plane straight-line drawing in which a subset S of its vertices are collinear, then for any set of points, X, in the plane with |X| = |S|, there is a plane straight-line drawing of G in which the vertices in S are mapped to the points in X. This solves an open problem posed by Ravsky and Verbitsky in 2008. In their terminology, we show that every collinear set is free. This result has applications in graph drawing, including untangling, column planarity, universal point subsets, and partial simultaneous drawings.

We consider a well studied generalization of the maximum clique problem which is defined as follows. Given a graph G on n vertices and an integer d >= 1, in the maximum diameter-bounded subgraph problem (MaxDBS for short), the goal is to find a (vertex) maximum subgraph of G of diameter at most d. For d=1, this problem is equivalent to the maximum clique problem and thus it is NP-hard to approximate it within a factor n^{1-epsilon}, for any epsilon > 0. Moreover, it is known that, for any d >= 2, it is NP-hard to approximate MaxDBS within a factor n^{1/2 - epsilon}, for any epsilon > 0. In this paper we focus on MaxDBS for the class of unit disk graphs. We provide a polynomial-time constant-factor approximation algorithm for the problem. The approximation ratio of our algorithm does not depend on the diameter d. Even though the algorithm itself is simple, its analysis is rather involved. We combine tools from the theory of hypergraphs with bounded VC-dimension, k-quasi planar graphs, fractional Helly theorems and several geometric properties of unit disk graphs.

An obstacle representation of a graph is a mapping of the vertices onto points in the plane and a set of connected regions of the plane (called obstacles) such that the straight-line segment connecting the points corresponding to two vertices does not intersect any obstacles if and only if the vertices are adjacent in the graph. The obstacle representation and its plane variant (in which the resulting representation is a plane straight-line embedding of the graph) have been extensively studied with the main objective of minimizing the number of obstacles. Recently, Biedl and Mehrabi [Therese C. Biedl and Saeed Mehrabi, 2017] studied non-blocking grid obstacle representations of graphs in which the vertices of the graph are mapped onto points in the plane while the straight-line segments representing the adjacency between the vertices is replaced by the L_1 (Manhattan) shortest paths in the plane that avoid obstacles. In this paper, we introduce the notion of geodesic obstacle representations of graphs with the main goal of providing a generalized model, which comes naturally when viewing line segments as shortest paths in the Euclidean plane. To this end, we extend the definition of obstacle representation by allowing some obstacles-avoiding shortest path between the corresponding points in the underlying metric space whenever the vertices are adjacent in the graph. We consider both general and plane variants of geodesic obstacle representations (in a similar sense to obstacle representations) under any polyhedral distance function in R^d as well as shortest path distances in graphs. Our results generalize and unify the notions of obstacle representations, plane obstacle representations and grid obstacle representations, leading to a number of questions on such representations.

This paper studies graphs that have two tree decompositions with the property that every bag from the first decomposition has a bounded-size intersection with every bag from the second decomposition. We show that every graph in each of the following classes has a tree decomposition and a linear-sized path decomposition with bounded intersections: (1) every proper minor-closed class, (2) string graphs with a linear number of crossings in a fixed surface, (3) graphs with linear crossing number in a fixed surface. Here “linear size” means that the total size of the bags in the path decomposition is $O(n)$ for $n$-vertex graphs. We then show that every $n$-vertex graph that has a tree decomposition and a linear-sized path decomposition with bounded intersections has $O(\sqrt{n})$ treewidth. As a corollary, we conclude a new lower bound on the crossing number of a graph in terms of its treewidth. Finally, we consider graph classes that have two path decompositions with bounded intersections. Trees and outerplanar graphs have this property. But for the next most simple class, series parallel graphs, we show that no such result holds.

The following is a corrigendum to [ Orthogonal tree decompositions of graphs, SIAM J. Discrete Math., 32 (2018), pp. 839--863].

Motivated by applications to graph morphing, we consider the following compatible connectivity-augmentation problem: We are given a labelled n-vertex planar graph, G, that has r ≥ 2 connected components, and k ≥ 2 isomorphic planar straight-line drawings, G1, …, G2, of G. We wish to augment G by adding vertices and edges to make it connected in such a way that these vertices and edges can be added to G1, …, G2 as points and straight-line segments, respectively, to obtain k planar straight-line drawings isomorphic to the augmentation of G. We show that adding Θ(nr1–1/k) edges and vertices to G is always sufficient and sometimes necessary to achieve this goal. The upper bound holds for all r ∊ {2, …, n} and k ≥ 2 and is achievable by an algorithm whose running time is O(nr1–1/k) for k = O(1) and whose running time is O(kn2) for general values of k. The lower bound holds for all r ∊ {2, …, n/4} and k ≥ 2.

Highly connected and yet sparse graphs (such as expanders or graphs of high treewidth) are fundamental, widely a pplicable and extensively studied combinatorial objects. We initiate the study of such highly connected graphs that are, in addition, geometric spanners. We define a property of spanners called robustness. Informally, when one removes a few vertices from a robust spanner, this harms only a small number of other vertices. We show that robust spanners must have a superlinear number of edges, even in one dimension. On the positive side, we give constructions, for any dimension, of robust spanners with a near-linear number of edges.

Graph separators are a ubiquitous tool in graph theory and computer science. However, in some applications, their usefulness is limited by the fact that the separator can be as large as Ω(√n) in graphs with n vertices. This is the case for planar graphs, and more generally, for proper minor-closed families. We study a special type of graph separator, called a layered separator, which may have linear size in n, but has bounded size with respect to a different measure, called the breadth. We prove that a wide class of graphs admit layered separators of bounded breadth, including graphs of bounded Euler genus. We use layered separators to prove Õ(log n) bounds for a number of problems where O(√n) was a long standing previous best bound. This includes the nonrepetitive chromatic number and queue-number of graphs with bounded Euler genus. We extend these results to all proper minor-closed families, with a O(log n) bound on the nonrepetitive chromatic number, and a logO(1)n bound on the queue-number. Only for planar graphs were logO(1)n bounds previously known. Our results imply that every graph from a proper minor-closed class has a 3-dimensional grid drawing with n logO(1)n volume, whereas the previous best bound was O(n3/2). Readers interested in the full details should consult arXiv:1302.0304 and arXiv:1306.1595, rather than the current extended abstract.

Highly connected and yet sparse graphs (such as expanders or graphs of high treewidth) are fundamental, widely applicable, and extensively studied combinatorial objects. We initiate the study of such highly connected graphs that are, in addition, geometric spanners. We define a property of spanners called robustness. Informally, when one removes a few vertices from a robust spanner, this harms only a small number of other vertices. We show that robust spanners must have a superlinear number of edges, even in one dimension. On the positive side, we give constructions, for any dimension, of robust spanners with a near-linear number of edges.

We propose designing data structures called succinct geometric indexes of negligible space (more precisely, o ( n ) bits) that support geometric queries in optimal time, by taking advantage of the n points in the dataset permuted and stored elsewhere as a sequence. Our first and main result is a succinct geometric index that can answer point location queries, a fundamental problem in computational geometry, on planar triangulations in O (lg n ) time. We also design three variants of this index. The first supports point location using lg n + 2√lg n + O (lg 1/4 n ) point-line comparisons. The second supports point location in o (lg n ) time when the coordinates are integers bounded by U . The last variant can answer point location queries in O ( H + 1) expected time, where H is the entropy of the query distribution. These results match the query efficiency of previous point location structures that occupy O ( n ) words or O(n lg n ) bits, while saving drastic amounts of space. We generalize our succinct geometric index to planar subdivisions, and design indexes for other types of queries. Finally, we apply our techniques to design the first implicit data structures that support point location in O (lg 2 n ) time.

A data structure is presented for point location in connected planar subdivisions when the distribution of queries is known in advance. The data structure has an expected query time that is within a constant factor of optimal. More specifically, an algorithm is presented that preprocesses a connected planar subdivision G of size n and a query distribution D to produce a point location data structure for G . The expected number of point-line comparisons performed by this data structure, when the queries are distributed according to D , is H˜ + O (H˜ 1/2 +1) where H˜=H˜( G,D ) is a lower bound on the expected number of point-line comparisons performed by any linear decision tree for point location in G under the query distribution D . The preprocessing algorithm runs in O ( n log n ) time and produces a data structure of size O ( n ). These results are obtained by creating a Steiner triangulation of G that has near-minimum entropy.

Suppose we want to compute the Delaunay triangulation of a set P whose points are restricted to a collection ℛ of input regions known in advance. Building on recent work by Löffler and Snoeyink, we show how to leverage our knowledge of ℛ for faster Delaunay computation. Our approach needs no fancy machinery and optimally handles a wide variety of inputs, e.g., overlapping disks of different sizes and fat regions.

We present a trade-off between the expected time for two identical agents to rendezvous on a synchronous, anonymous, oriented ring and the memory requirements of the agents. In particular, we show there exists a 2 t state agent which can achieve rendezvous on an n -node ring in expected time O ( n 2 /2 t + 2 t ) and that any t /2 state agent requires expected time Ω( n 2 /2 t ). As a corollary we observe that Θ(log log n ) bits of memory are necessary and sufficient to achieve rendezvous in linear time.

In this paper we consider query versions of visibility testing and visibility counting. Let S be a set of n disjoint line segments in ℜ2 and let s be an element of S. Visibility testing is to preprocess S so that we can quickly determine if s is visible from a query point q. Visibility counting involves preprocessing S so that one can quickly estimate the number of segments in S visible from a query point q.

We propose to design data structures called succinct geometric indexes of negligible space (more precisely, o(n) bits) that support geometric queries in optimal time, by taking advantage of the n points in the data set permuted and stored elsewhere as a sequence. Our first and main result is a succinct geometric index that can answer point location queries, a fundamental problem in computational geometry, on planar triangulations in O(lg n) time. We also design three variants of this index. The first supports point location using point-line comparisons. The second supports point location in o(lg n) time when the coordinates are integers bounded by U. The last variant can answer point location queries in O(H + 1) expected time, where H is the entropy of the query distribution. These results match the query efficiency of previous point location structures that occupy O(n) words or O(n lg n) bits, while saving drastic amounts of space. We generalize our succinct geometric index to planar subdivisions, and design indexes for other types of queries. Finally, we apply our techniques to design the first implicit data structures that support point location in O(lg2 n) time.

A data structure, called a biased range tree, is presented that preprocesses a set S of n points in ℝ2 and a query distribution D for 2-sided orthogonal range counting queries. The expected query time for this data structure, when queries are drawn according to D, matches, to within a constant factor, that of the optimal comparison tree for S and D. The memory and preprocessing requirements of the data structure are O(n log n).

We address the following problem: Given a complete k-partite geometric graph K whose vertex set is a set of n points in $\mathbb{R}^d$, compute a spanner of K that has a “small” stretch factor and “few” edges. We present two algorithms for this problem. The first algorithm computes a $(5+\epsilon)$-spanner of K with $O(n)$ edges in $O(n\log n)$ time. The second algorithm computes a $(3+\epsilon)$-spanner of K with $O(n\log n)$ edges in $O(n \log n)$ time. The latter result is optimal: We show that for any $2\leq k\leq n-\Theta(\sqrt{n\log n})$, spanners with $O(n\log n)$ edges and stretch factor less than 3 do not exist for all complete k-partite geometric graphs.

Aqueue layout of a graph consists of a total order of the vertices, and a partition of the edges into queues, such that no two edges in the same queue are nested. The minimum number of queues in a queue layout of a graph is its queue-number. A three-dimensional (straight-line grid) drawing of a graph represents the vertices by points in $\mathbb{Z}^3$ and the edges by noncrossing line-segments. This paper contributes three main results: (1) It is proved that the minimum volume of a certain type of three-dimensional drawing of a graph G is closely related to the queue-number of G. In particular, if G is an n-vertex member of a proper minor-closed family of graphs (such as a planar graph), then G has a $\mathcal{O}(1) \times \mathcal{O}(1) \times \mathcal{O}(n)$ drawing if and only if G has a $\mathcal{O}(1)$ queue-number. (2) It is proved that the queue-number is bounded by the tree-width, thus resolving an open problem due to Ganley and Heath [Discrete Appl. Math., 109 (2001), pp. 215--221] and disproving a conjecture of Pemmaraju [Exploring the Powers of Stacks and Queues via Graph Layouts, Ph. D. thesis, Virginia Polytechnic Institute and State University, Blacksburg, VA, 1992]. This result provides renewed hope for the positive resolution of a number of open problems in the theory of queue layouts. (3) It is proved that graphs of bounded tree-width have three-dimensional drawings with $\mathcal{O}(n)$ volume. This is the most general family of graphs known to admit three-dimensional drawings with $\mathcal{O}(n)$ volume. The proofs depend upon our results regarding track layouts and tree-partitions of graphs, which may be of independent interest.

Let P be a simple polygon with m vertices, k of which are reflex, and which contains r red points and b blue points in its interior. Let n=m+r+b. A ham-sandwich geodesic is a shortest path in P between any two points on the boundary of P that simultaneously bisects the red points and the blue points. We present an O (n log k)-time algorithm for finding a ham-sandwich geodesic. We also show that this algorithm is optimal in thealgebraic computation tree model when parameterizing the running time with respect to n and k.

We consider online routing algorithms for routing between the vertices of embedded planar straight line graphs. Our results include (1) two deterministic memoryless routing algorithms, one that works for all Delaunay triangulations and the other that works for all regular triangulations; (2) a randomized memoryless algorithm that works for all triangulations; (3) an O(1) memory algorithm that works for all convex subdivisions; (4) an O(1) memory algorithm that approximates the shortest path in Delaunay triangulations; and (5) theoretical and experimental results on the competitiveness of these algorithms.

We consider open addressing hashing and implement it by using the Robin Hood strategy; that is, in case of collision, the element that has traveled the farthest can stay in the slot. We hash $\sim \alpha n$ elements into a table of size n where each probe is independent and uniformly distributed over the table, and $\alpha < 1$ is a constant. Let $M_n$ be the maximum search time for any of the elements in the table. We show that with probability tending to one, $M_n \in [ \log_2 \log n + \sigma, \log_2 \log n + \tau ]$ for some constants $\sigma, \tau$ depending upon $\alpha$ only. This is an exponential improvement over the maximum search time in case of the standard FCFS (firstcome first served) collision strategy and virtually matches the performance of multiple-choice hash methods.