BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Vida Dujmovic

Vida Dujmovic appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computational GeometryData Structures and AlgorithmsDiscrete Mathematicsmath.CONetworking and Internet Architecturemath.MGmath.STStatistics Theory

Catalog footprint

What is connected

16works
8topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

16 published item(s)

preprint2016arXiv

Drawing Planar Graphs with Many Collinear Vertices

Consider the following problem: Given a planar graph $G$, what is the maximum number $p$ such that $G$ has a planar straight-line drawing with $p$ collinear vertices? This problem resides at the core of several graph drawing problems, including universal point subsets, untangling, and column planarity. The following results are known for it: Every $n$-vertex planar graph has a planar straight-line drawing with $Ω(\sqrt{n})$ collinear vertices; for every $n$, there is an $n$-vertex planar graph whose every planar straight-line drawing has $O(n^σ)$ collinear vertices, where $σ<0.986$; every $n$-vertex planar graph of treewidth at most two has a planar straight-line drawing with $Θ(n)$ collinear vertices. We extend the linear bound to planar graphs of treewidth at most three and to triconnected cubic planar graphs. This (partially) answers two open problems posed by Ravsky and Verbitsky [WG 2011:295--306]. Similar results are not possible for all bounded treewidth planar graphs or for all bounded degree planar graphs. For planar graphs of treewidth at most three, our results also imply asymptotically tight bounds for all of the other above mentioned graph drawing problems.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Average Stretch Factor: How Low Does It Go?

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 $\mathbb{R}^d$, there exists a geometric graph with vertex set $V$, that has $O(n)$ edges, and that has average stretch factor $1+ o_n(1)$. More precisely, the average stretch factor of this graph is $1+O((\log n/n)^{1/(2d+1)})$. We complement this upper-bound with a lower bound: There exist $n$-point sets in $\mathbb{R}^2$ for which any graph with $O(n)$ edges has average stretch factor $1+Ω(1/\sqrt{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+o_n(1)$ has a superlinear number of edges.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Crossings in Grid Drawings

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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Graph Layouts via Layered Separators

A k-queue layout of a graph consists of a total order of the vertices, and a partition of the edges into k sets such that no two edges that are in the same set are nested with respect to the vertex ordering. A k-track layout of a graph consists of a vertex k-colouring, and a total order of each vertex colour class, such that between each pair of colour classes no two edges cross. The queue-number (track-number) of a graph G, is the minimum k such that G has a k-queue (k-track) layout. This paper proves that every n-vertex planar graph has track number and queue number at most O(log n). This improves the result of Di Battista, Frati and Pach [Foundations of Computer Science, (FOCS '10), pp. 365--374] who proved the first sub-polynomial bounds on the queue number and track number of planar graphs. Specifically, they obtained O(log^2 n) queue number and O(log^8 n) track number bounds for planar graphs. The result also implies that every planar graph has a 3D crossing-free grid drawing in O(n log n) volume. The proof uses a non-standard type of graph separators.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Robust Geometric Spanners

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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A Center Transversal Theorem for Hyperplanes and Applications to Graph Drawing

Motivated by an open problem from graph drawing, we study several partitioning problems for line and hyperplane arrangements. We prove a ham-sandwich cut theorem: given two sets of n lines in R^2, there is a line l such that in both line sets, for both halfplanes delimited by l, there are n^{1/2} lines which pairwise intersect in that halfplane, and this bound is tight; a centerpoint theorem: for any set of n lines there is a point such that for any halfplane containing that point there are (n/3)^{1/2} of the lines which pairwise intersect in that halfplane. We generalize those results in higher dimension and obtain a center transversal theorem, a same-type lemma, and a positive portion Erdos-Szekeres theorem for hyperplane arrangements. This is done by formulating a generalization of the center transversal theorem which applies to set functions that are much more general than measures. Back to Graph Drawing (and in the plane), we completely solve the open problem that motivated our search: there is no set of n labelled lines that are universal for all n-vertex labelled planar graphs. As a side note, we prove that every set of n (unlabelled) lines is universal for all n-vertex (unlabelled) planar graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Notes on large angle crossing graphs

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.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Odds-On Trees

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.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Point Location in Disconnected Planar Subdivisions

Let $G$ be a (possibly disconnected) planar subdivision and let $D$ be a probability measure over $\R^2$. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Entropy, Triangulation, and Point Location in Planar Subdivisions

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.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Memoryless Routing in Convex Subdivisions: Random Walks are Optimal

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.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

A polynomial bound for untangling geometric planar graphs

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}.

0 citations0 reviewsNo code linkedOpen access
preprint2004arXiv

Layout of Graphs with Bounded Tree-Width

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 $\mathbb{Z}^3$ 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)\times O(1)\times 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.

0 citations0 reviewsNo code linkedOpen access
preprint2004arXiv

Track Layouts of Graphs

A \emph{$(k,t)$-track layout} of a graph $G$ consists of a (proper) vertex $t$-colouring of $G$, a total order of each vertex colour class, and a (non-proper) edge $k$-colouring such that between each pair of colour classes no two monochromatic edges cross. This structure has recently arisen in the study of three-dimensional graph drawings. This paper presents the beginnings of a theory of track layouts. First we determine the maximum number of edges in a $(k,t)$-track layout, and show how to colour the edges given fixed linear orderings of the vertex colour classes. We then describe methods for the manipulation of track layouts. For example, we show how to decrease the number of edge colours in a track layout at the expense of increasing the number of tracks, and vice versa. We then study the relationship between track layouts and other models of graph layout, namely stack and queue layouts, and geometric thickness. One of our principle results is that the queue-number and track-number of a graph are tied, in the sense that one is bounded by a function of the other. As corollaries we prove that acyclic chromatic number is bounded by both queue-number and stack-number. Finally we consider track layouts of planar graphs. While it is an open problem whether planar graphs have bounded track-number, we prove bounds on the track-number of outerplanar graphs, and give the best known lower bound on the track-number of planar graphs.

0 citations0 reviewsNo code linkedOpen access