BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We prove that for every tree T of radius h, there is an integer c such that every T-minor-free graph is contained in H⊠Kc for some graph H with pathwidth at most 2h−1. This is a qualitative strengthening of the Excluded Tree Minor Theorem of Robertson and Seymour (GM I). We show that radius is the right parameter to consider in this setting, and 2h−1 is the best possible bound.
The \emph{Product Structure Theorem} for planar graphs (Dujmović et al.\ \emph{JACM}, \textbf{67}(4):22) states that any planar graph is contained in the strong product of a planar 3-tree, a path, and a 3-cycle. We give a simple linear-time algorithm for finding this decomposition as well as several related decompositions. This improves on the previous O(nlogn) time algorithm (Morin.\ \emph{Algorithmica}, \textbf{85}(5):1544--1558).
A (vertex) ℓ-ranking is a colouring φ:V(G)→N of the vertices of a graph G with integer colours so that for any path u0,…,up of length at most ℓ, φ(u0)=φ(up) or φ(u0)<max{φ(u0),…,φ(up)}. We show that, for any fixed integer ℓ≥2, every n-vertex planar graph has an ℓ-ranking using O(logn/logloglogn) colours and this is tight even when ℓ=2; for infinitely many values of n, there are n-vertex planar graphs, for which any 2-ranking requires Ω(logn/logloglogn) colours. This result also extends to bounded genus graphs. In developing this proof we obtain optimal bounds on the number of colours needed for ℓ-ranking graphs of treewidth t and graphs of simple treewidth t. These upper bounds are constructive and give O(n)-time algorithms. Additional results that come from our techniques include new sublogarithmic upper bounds on the number of colours needed for ℓ-rankings of apex minor-free graphs and k-planar graphs.
The odd colouring number is a new graph parameter introduced by Petruševski and Škrekovski. In this note, we show that graphs with so called product structure have bounded odd-colouring number. By known results on the product structure of k-planar graphs, this implies that k-planar graphs have bounded odd-colouring number, which answers a question of Cranston, Lafferty, and Song.
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).
We study the problem of embedding graphs in the plane as good geometric spanners. That is, for a graph G, the goal is to construct a straight-line drawing Γ of G in the plane such that, for any two vertices u and v of G, the ratio between the minimum length of any path from u to v and the Euclidean distance between u and v is small. The maximum such ratio, over all pairs of vertices of G, is the spanning ratio of Γ. First, we show that deciding whether a graph admits a straight-line drawing with spanning ratio 1, a proper straight-line drawing with spanning ratio 1, and a planar straight-line drawing with spanning ratio 1 are NP-complete, ∃R-complete, and linear-time solvable problems, respectively, where a drawing is proper if no two vertices overlap and no edge overlaps a vertex. Second, we show that moving from spanning ratio 1 to spanning ratio 1+ε allows us to draw every graph. Namely, we prove that, for every ε>0, every (planar) graph admits a proper (resp. planar) straight-line drawing with spanning ratio smaller than 1+ε. Third, our drawings with spanning ratio smaller than 1+ε have large edge-length ratio, that is, the ratio between the length of the longest edge and the length of the shortest edge is exponential. We show that this is sometimes unavoidable. More generally, we identify having bounded toughness as the criterion that distinguishes graphs that admit straight-line drawings with constant spanning ratio and polynomial edge-length ratio from graphs that require exponential edge-length ratio in any straight-line drawing with constant spanning ratio.
We show that, if a n-vertex triangulation T of maximum degree Δ has a dual that contains a cycle of length ℓ, then T has a non-crossing straight-line drawing in which some \emph{collinear set} of Ω(ℓ/Δ4) vertices lie on a line. Using the current lower bounds on the length of longest cycles in 3-regular 3-connected graphs, this implies that every n-vertex planar graph of maximum degree Δ has a collinear set of size Ω(n0.8/Δ4). Very recently, Dujmović et. al. (SODA 2019) showed that, if S is a collinear set in a triangulation T then, for any point set X⊂R2 with ∣X∣=∣S∣, T has a non-crossing straight-line drawing in which the vertices of S are drawn on the points in X. Because of this, collinear sets have numerous applications in graph drawing and related areas.
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 generalises 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 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. (2004) that graphs in a proper minor-closed class have low treewidth colourings.
In their seminal work, Danzer (1956, 1986) and Stachó (1981) established that every set of pairwise intersecting disks in the plane can be stabbed by four points. However, both these proofs are non-constructive, at least in the sense that they do not seem to imply an efficient algorithm for finding the stabbing points, given such a set of disks D. Recently, Har-Peled \etal (2018) presented a relatively simple linear-time algorithm for finding five points that stab D. We present an alternative proof (and the first in English) to the assertion that four points are sufficient to stab D. Moreover, our proof is constructive and provides a simple linear-time algorithm for finding the stabbing points. As a warmup, we present a nearly-trivial liner-time algorithm with an elementary proof for finding five points that stab D.
Layered pathwidth is a new graph parameter studied by Bannister et al (2015). In this paper we present two new results relating layered pathwidth to two types of linear layouts. Our first result shows that, for any graph G, the stack number of G is at most four times the layered pathwidth of G. Our second result shows that any graph G with track number at most three has layered pathwidth at most four. The first result complements a result of Dujmović and Frati (2018) relating layered treewidth and stack number. The second result solves an open problem posed by Bannister et al (2015).
We prove that the facial nonrepetitive chromatic number of any outerplanar graph is at most 11 and of any planar graph is at most 22.
Let R and B be two disjoint sets of points in the plane where the points of R are colored red and the points of B are colored blue, and let n=∣R∪B∣. A bichromatic spanning tree is a spanning tree in the complete bipartite geometric graph with bipartition (R,B). The minimum (respectively maximum) bichromatic spanning tree problem is the problem of computing a bichromatic spanning tree of minimum (respectively maximum) total edge length. 1. We present a simple algorithm that solves the minimum bichromatic spanning tree problem in O(nlog3n) time. This algorithm can easily be extended to solve the maximum bichromatic spanning tree problem within the same time bound. It also can easily be generalized to multicolored point sets. 2. We present Θ(nlogn)-time algorithms that solve the minimum and the maximum bichromatic spanning tree problems. 3. We extend the bichromatic spanning tree algorithms and solve the multicolored version of these problems in O(nlognlogk) time, where k is the number of different colors (or the size of the multipartition in a complete multipartite geometric graph).
We present tight bounds on the spanning ratio of a large family of ordered θ-graphs. A θ-graph partitions the plane around each vertex into m disjoint cones, each having aperture θ=2π/m. An ordered θ-graph is constructed by inserting the vertices one by one and connecting each vertex to the closest previously-inserted vertex in each cone. We show that for any integer k≥1, ordered θ-graphs with 4k+4 cones have a tight spanning ratio of 1+2sin(θ/2)/(cos(θ/2)−sin(θ/2)). We also show that for any integer k≥2, ordered θ-graphs with 4k+2 cones have a tight spanning ratio of 1/(1−2sin(θ/2)). We provide lower bounds for ordered θ-graphs with 4k+3 and 4k+5 cones. For ordered θ-graphs with 4k+2 and 4k+5 cones these lower bounds are strictly greater than the worst case spanning ratios of their unordered counterparts. These are the first results showing that ordered θ-graphs have worse spanning ratios than unordered θ-graphs. Finally, we show that, unlike their unordered counterparts, the ordered θ-graphs with 4, 5, and 6 cones are not spanners.
Motivated by applications to graph morphing, we consider the following \emph{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,…,Gk, 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,…,Gk 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.
Given a set of points in the plane, we show that the θ-graph with 5 cones is a geometric spanner with spanning ratio at most 50+225≈9.960. This is the first constant upper bound on the spanning ratio of this graph. The upper bound uses a constructive argument that gives a (possibly self-intersecting) path between any two vertices, of length at most 50+225 times the Euclidean distance between the vertices. We also give a lower bound on the spanning ratio of 21(115−17)≈3.798.
We describe todolists (top-down skiplists), a variant of skiplists (Pugh 1990) that can execute searches using at most log2−εn+O(1) binary comparisons per search and that have amortized update time O(ε−1logn). A variant of todolists, called working-todolists, can execute a search for any element x using log2−εw(x)+o(logw(x)) binary comparisons and have amortized search time O(ε−1logw(w)). Here, w(x) is the "working-set number" of x. No previous data structure is known to achieve a bound better than 4log2w(x) comparisons. We show through experiments that, if implemented carefully, todolists are comparable to other common dictionary implementations in terms of insertion times and outperform them in terms of search times.
We present improved upper and lower bounds on the spanning ratio of θ-graphs with at least six cones. Given a set of points in the plane, a θ-graph partitions the plane around each vertex into m disjoint cones, each having aperture θ=2π/m, and adds an edge to the `closest' vertex in each cone. We show that for any integer k≥1, θ-graphs with 4k+2 cones have a spanning ratio of 1+2sin(θ/2) and we provide a matching lower bound, showing that this spanning ratio tight. Next, we show that for any integer k≥1, θ-graphs with 4k+4 cones have spanning ratio at most 1+2sin(θ/2)/(cos(θ/2)−sin(θ/2)). We also show that θ-graphs with 4k+3 and 4k+5 cones have spanning ratio at most cos(θ/4)/(cos(θ/2)−sin(3θ/4)). This is a significant improvement on all families of θ-graphs for which exact bounds are not known. For example, the spanning ratio of the θ-graph with 7 cones is decreased from at most 7.5625 to at most 3.5132. These spanning proofs also imply improved upper bounds on the competitiveness of the θ-routing algorithm. In particular, we show that the θ-routing algorithm is (1+2sin(θ/2)/(cos(θ/2)−sin(θ/2)))-competitive on θ-graphs with 4k+4 cones and that this ratio is tight. Finally, we present improved lower bounds on the spanning ratio of these graphs. Using these bounds, we provide a partial order on these families of θ-graphs. In particular, we show that θ-graphs with 4k+4 cones have spanning ratio at least 1+2tan(θ/2)+2tan2(θ/2). This is somewhat surprising since, for equal values of k, the spanning ratio of θ-graphs with 4k+4 cones is greater than that of θ-graphs with 4k+2 cones, showing that increasing the number of cones can make the spanning ratio worse.
We consider the problem of approximating the majority depth (Liu and Singh, 1993) of a point q with respect to an n-point set, S, by random sampling. At the heart of this problem is a data structures question: How can we preprocess a set of n lines so that we can quickly test whether a randomly selected vertex in the arrangement of these lines is above or below the median level. We describe a Monte-Carlo data structure for this problem that can be constructed in O(nlog n) time, can answer queries O((log n)^{4/3}) expected time, and answers correctly with high probability.
In a geometric graph, G, the \emph{stretch factor} between two vertices, u and w, is the ratio between the Euclidean length of the shortest path from u to w in G and the Euclidean distance between u and w. The \emph{average stretch factor} of G is the average stretch factor taken over all pairs of vertices in G. We show that, for any constant dimension, d, and any set, V, of n points in Rd, there exists a geometric graph with vertex set V, that has O(n) edges, and that has average stretch factor 1+on(1). More precisely, the average stretch factor of this graph is 1+O((logn/n)1/(2d+1)). We complement this upper-bound with a lower bound: There exist n-point sets in R2 for which any graph with O(n) edges has average stretch factor 1+Ω(1/n). Bounds of this type are not possible for the more commonly studied worst-case stretch factor. In particular, there exists point sets, V, such that any graph with worst-case stretch factor 1+on(1) has a superlinear number of edges.
We prove crossing number inequalities for geometric graphs whose vertex sets are taken from a d-dimensional grid of volume N and give applications of these inequalities to counting the number of non-crossing geometric graphs that can be drawn on such grids. In particular, we show that any geometric graph with m >= 8N edges and with vertices on a 3D integer grid of volume N, has Ω((m^2/n)\log(m/n)) crossings. In d-dimensions, with d >= 4, this bound becomes Ω(m^2/n). We provide matching upper bounds for all d. Finally, for d >= 4 the upper bound implies that the maximum number of crossing-free geometric graphs with vertices on some d-dimensional grid of volume N is n^Θ(n). In 3 dimensions it remains open to improve the trivial bounds, namely, the 2^Ω(n) lower bound and the n^O(n) upper bound.
The obstacle number is a new graph parameter introduced by Alpert, Koch, and Laison (2010). Mukkamala etal (2012) show that there exist graphs with n vertices having obstacle number in Omega(n/\log n). In this note, we up this lower bound to Omega(n/(\log\log n)^2. Our proof makes use of an upper bound of Mukkamala etal on the number of graphs having obstacle number at most h in such a way that any subsequent improvements to their upper bound will improve our lower bound.
Theta graphs are important geometric graphs that have many applications, including wireless networking, motion planning, real-time animation, and minimum-spanning tree construction. We give closed form expressions for the average degree of theta graphs of a homogeneous Poisson point process over the plane. We then show that essentially the same bounds---with vanishing error terms---hold for theta graphs of finite sets of points that are uniformly distributed in a square. Finally, we show that the number of edges in a theta graph of points uniformly distributed in a square is concentrated around its expected value.
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.
The unified property roughly states that searching for an element is fast when the current access is close to a recent access. Here, "close" refers to rank distance measured among all elements stored by the dictionary. We show that distance need not be measured this way: in fact, it is only necessary to consider a small working-set of elements to measure this rank distance. This results in a data structure with access time that is an improvement upon those offered by the unified property for many query sequences.
Consider n sensors whose positions are represented by n uniform, independent and identically distributed random variables assuming values in the open unit interval (0,1). A natural way to guarantee connectivity in the resulting sensor network is to assign to each sensor as its range, the maximum of the two possible distances to its two neighbors. The interference at a given sensor is defined as the number of sensors that have this sensor within their range. In this paper we prove that the expected maximum interference of the sensors is Θ(lnn).
Consider a sequence of bit strings of length d, such that each string differs from the next in a constant number of bits. We call this sequence a quasi-Gray code. We examine the problem of efficiently generating such codes, by considering the number of bits read and written at each generating step, the average number of bits read while generating the entire code, and the number of strings generated in the code. Our results give a trade-off between these constraints, and present algorithms that do less work on average than previous results, and that increase the number of bit strings generated.
A graph G is an a-angle crossing (aAC) graph if every pair of crossing edges in G intersect at an angle of at least a. The concept of right angle crossing (RAC) graphs (a=Pi/2) was recently introduced by Didimo et. al. It was shown that any RAC graph with n vertices has at most 4n-10 edges and that there are infinitely many values of n for which there exists a RAC graph with n vertices and 4n-10 edges. In this paper, we give upper and lower bounds for the number of edges in aAC graphs for all 0 < a < Pi/2.
Let R^d -> A be a query problem over R^d for which there exists a data structure S that can compute P(q) in O(log n) time for any query point q in R^d. Let D be a probability measure over R^d representing a distribution of queries. We describe a data structure called the odds-on tree, of size O(n^ε) that can be used as a filter that quickly computes P(q) for some query values q in R^d and relies on S for the remaining queries. With an odds-on tree, the expected query time for a point drawn according to D is O(H*+1), where H* is a lower-bound on the expected cost of any linear decision tree that solves P. Odds-on trees have a number of applications, including distribution-sensitive data structures for point location in 2-d, point-in-polytope testing in d dimensions, ray shooting in simple polygons, ray shooting in polytopes, nearest-neighbour queries in R^d, point-location in arrangements of hyperplanes in R^d, and many other geometric searching problems that can be solved in the linear-decision tree model. A standard lifting technique extends these results to algebraic decision trees of constant degree. A slightly different version of odds-on trees yields similar results for orthogonal searching problems that can be solved in the comparison tree model.
In this paper we consider query versions of visibility testing and visibility counting. Let S be a set of n disjoint line segments in R2 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 present several data structures for the two query problems. The structures build upon a result by O'Rourke and Suri (1984) who showed that the subset, VS(s), of R2 that is weakly visible from a segment s can be represented as the union of a set, CS(s), of O(n2) triangles, even though the complexity of VS(s) can be Ω(n4). We define a variant of their covering, give efficient output-sensitive algorithms for computing it, and prove additional properties needed to obtain approximation bounds. Some of our bounds rely on a new combinatorial result that relates the number of segments of S visible from a point p to the number of triangles in ⋃s∈SCS(s) that contain p.
Let G be a (possibly disconnected) planar subdivision and let D be a probability measure over R2. The current paper shows how to preprocess (G,D) into an O(n) size data structure that can answer planar point location queries over G. The expected query time of this data structure, for a query point drawn according to D, is O(H+1), where H is a lower bound on the expected query time of any linear decision tree for point location in G. This extends the results of Collette et al (2008, 2009) from connected planar subdivisions to disconnected planar subdivisions. A version of this structure, when combined with existing results on succinct point location, provides a succinct distribution-sensitive point location structure.
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^{2/3}+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.
A memoryless routing algorithm is one in which the decision about the next edge on the route to a vertex t for a packet currently located at vertex v is made based only on the coordinates of v, t, and the neighbourhood, N(v), of v. The current paper explores the limitations of such algorithms by showing that, for any (randomized) memoryless routing algorithm A, there exists a convex subdivision on which A takes Omega(n^2) expected time to route a message between some pair of vertices. Since this lower bound is matched by a random walk, this result implies that the geometric information available in convex subdivisions is not helpful for this class of routing algorithms. The current paper also shows the existence of triangulations for which the Random-Compass algorithm proposed by Bose etal (2002,2004) requires 2^{Ω(n)} time to route between some pair of vertices.
To untangle a geometric graph means to move some of the vertices so that the resulting geometric graph has no crossings. Pach and Tardos [Discrete Comput. Geom., 2002] asked if every n-vertex geometric planar graph can be untangled while keeping at least n^εvertices fixed. We answer this question in the affirmative with ε=1/4. The previous best known bound was Ω((\log n / \log\log n)^{1/2}). We also consider untangling geometric trees. It is known that every n-vertex geometric tree can be untangled while keeping at least (n/3)^{1/2} vertices fixed, while the best upper bound was O(n\log n)^{2/3}. We answer a question of Spillner and Wolff [arXiv:0709.0170 2007] by closing this gap for untangling trees. In particular, we show that for infinitely many values of n, there is an n-vertex geometric tree that cannot be untangled while keeping more than 3(n^{1/2}-1) vertices fixed. Moreover, we improve the lower bound to (n/2)^{1/2}.
A graph G is a 2-tree if G=K_3, or G has a vertex v of degree 2, whose neighbours are adjacent, and Gǐs a 2-tree. A characterization of the degree sequences of 2-trees is given. This characterization yields a linear-time algorithm for recognizing and realizing degree sequences of 2-trees.
A \emph{queue layout} of a graph consists of a total order of the vertices, and a partition of the edges into \emph{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 \emph{queue-number}. A \emph{three-dimensional (straight-line grid) drawing} of a graph represents the vertices by points in Z3 and the edges by non-crossing 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 O(1)×O(1)×O(n) drawing if and only if G has O(1) queue-number. (2) It is proved that queue-number is bounded by tree-width, thus resolving an open problem due to Ganley and Heath (2001), and disproving a conjecture of Pemmaraju (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 O(n) volume. This is the most general family of graphs known to admit three-dimensional drawings with O(n) volume. The proofs depend upon our results regarding \emph{track layouts} and \emph{tree-partitions} of graphs, which may be of independent interest.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.