Memoryless Routing in Convex Subdivisions: Random Walks are Optimal (2009)
Chen, Dan, Devroye, Luc, Dujmovic, Vida, Morin, Pat
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,...
Notes on large angle crossing graphs (2009)
Dujmovic, Vida, Gudmundsson, Joachim, Morin, Pat, Wolle, Thomas
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...
Minimum feature size preserving decompositions (2009)
Aloupis, Greg, Demaine, Erik D., Demaine, Martin L., Dujmovic, Vida, Iacono, John
The minimum feature size of a crossing-free straight line drawing is the minimum distance between a vertex and a non-incident edge. This quantity measures the resolution needed to display a figure or...
Entropy, Triangulation, and Point Location in Planar Subdivisions (2009)
Collette, Sebastien, Dujmovic, Vida, Iacono, John, Langerman, Stefan, Morin, Pat
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...
Dujmovic, Vida, Howat, John, Morin, Pat
A data structure, called a biased range tree, is presented that preprocesses a set S of n points in R^2 and a query distribution D for 2-sided orthogonal range counting queries. The expected query...
Vida Dujmovic, Pat Morin, David R. Wood
Abstract. We prove that every n-vertex graph G with pathwidth pw(G) has a three-dimensional straight-line grid drawing with O(pw(G) 2 n) volume. Thus for graphs with bounded pathwidth the volume is...
n). No better bound than O(n (2007)
Vida Dujmovic, Pat Morin, David R. Wood
We prove that every n-vertex graph G with pathwidth pw(G) has a threedimensional straight line grid drawing with O(pw(G) 2 n) volume. Thus for graphs with bounded pathwidth the volume is O(n), and it...
Flat-State Connectivity of Linkages under Dihedral Motions (2007)
Greg Aloupis, Erik D. Demaine, Vida Dujmovic, Jeff Erickson, Stefan Langerman, Henk Meijer, ...
We explore which classes of linkages have the property that each pair of their at states|that is, their embeddings in R without self-intersection|can be connected by a continuous dihedral motion that...
A polynomial bound for untangling geometric planar graphs (2007)
Bose, Prosenjit, Dujmovic, Vida, Hurtado, Ferran, Langerman, Stefan, Morin, Pat, Wood, David R.
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...
Lines and free line segments Tangent to Arbitrary Three-dimensional Convex Polyhedra (2007)
Bronnimann, Hervé, Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...
Motivated by visibility problems in three dimensions, we investigate the complexity and construction of the set of tangent lines in a scene of three-dimensional polyhedra. We prove that the set of...
Lines and free line segments Tangent to Arbitrary Three-dimensional Convex Polyhedra (2007)
Bronnimann, Hervé, Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...
Motivated by visibility problems in three dimensions, we investigate the complexity and construction of the set of tangent lines in a scene of three-dimensional polyhedra. We prove that the set of...
Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint (2007)
Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Hornus, Samuel, Whitesides, Sue, Wismath, Steve
Given a set of n points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint q and efficiently maintaining this ordering information as q moves. In...
Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint (2007)
Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Hornus, Samuel, Whitesides, Sue, Wismath, Steve
Given a set of n points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint q and efficiently maintaining this ordering information as q moves. In...
Graph Treewidth and Geometric Thickness Parameters (2006)
Dujmovic, Vida, Wood, David R.
Consider a drawing of a graph G in the plane such that crossing edges are coloured differently. The minimum number of colours, taken over all drawings of G, is the classical graph parameter thickness...
Graph Treewidth and Geometric Thickness Parameters (2006)
Dujmovic, Vida, Wood, David R.
Consider a drawing of a graph G in the plane such that crossing edges are coloured differently. The minimum number of colours, taken over all drawings of G, is the classical graph parameter thickness...
Graph Treewidth and Geometric Thickness Parameters (2006)
Dujmovic, Vida, Wood, David R.
Consider a drawing of a graph G in the plane such that crossing edges are coloured differently. The minimum number of colours, taken over all drawings of G, is the classical graph parameter thickness...
Brönnimann, Hervé, Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...
We prove that the lines tangent to four possibly intersecting convex polyhedra in $^3$ with $n$ edges in total form $\Theta(n^2)$ connected components in the worst case. In the generic case, each...
Brönnimann, Hervé, Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...
We prove that the lines tangent to four possibly intersecting convex polyhedra in $^3$ with $n$ edges in total form $\Theta(n^2)$ connected components in the worst case. In the generic case, each...
Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint (2005)
Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Hornus, Samuel, Whitesides, Sue, Wismath, Steve
Given a set of $n$ points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint $q$ and efficiently maintaining this ordering information as $q$...
Induced Subgraphs of Bounded Degree and Bounded Treewidth (2005)
Bose, Prosenjit, Dujmovic, Vida, Wood, David R.
We prove that for all $0\leq t\leq k$ and $d\geq 2k$, every graph $G$ with treewidth at most $k$ has a `large' induced subgraph $H$, where $H$ has treewidth at most $t$ and every vertex in $H$ has...
Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint (2005)
Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Hornus, Samuel, Wismath, Steve, Whitesides, Sue
Given a set of n points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint q and efficiently maintaining this ordering information as q moves.
Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint (2005)
Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Hornus, Samuel, Wismath, Steve, Whitesides, Sue
Given a set of n points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint q and efficiently maintaining this ordering information as q moves.
Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint (2005)
Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Hornus, Samuel, Whitesides, Sue, Wismath, Steve
Given a set of $n$ points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint $q$ and efficiently maintaining this ordering information as $q$...
Brönnimann, Hervé, Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...
We prove that the lines tangent to four possibly intersecting convex polyhedra in $ ^3$ with $n$ edges in total form $\Theta(n^2)$ connected components in the worst case. In the generic case, each...
Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint (2005)
Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Hornus, Samuel, Whitesides, Sue, Wismath, Steve
Given a set of $n$ points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint $q$ and efficiently maintaining this ordering information as $q$...
Brönnimann, Hervé, Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...
We prove that the lines tangent to four possibly intersecting convex polyhedra in $ ^3$ with $n$ edges in total form $\Theta(n^2)$ connected components in the worst case. In the generic case, each...
Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint (2005)
Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Hornus, Samuel, Wismath, Steve, Whitesides, Sue
Given a set of n points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint q and efficiently maintaining this ordering information as q moves.
Track Layouts of Graphs (2004)
Dujmovic, Vida, Por, Attila, Wood, David R.
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...
Layout of Graphs with Bounded Tree-Width (2004)
Dujmovic, Vida, Morin, Pat, Wood, David R.
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...
Really Straight Graph Drawings (2004)
Dujmovic, Vida, Suderman, Matthew, Wood, David R.
This paper has been withdrawn by the authors. It has been replaced by the papers: "Drawings of Planar Graphs with Few Slopes and Segments" (math/0606450) and "Graph Drawings with Few Slopes"...
Three-Dimensional Grid Drawings with Sub-quadratic Volume (2004)
Dujmovic, Vida, Wood, David R.
A three-dimensional grid drawing of a graph is a placement of the vertices at distinct points with integer coordinates, such that the straight line-segments representing the edges are pairwise...
Fixed Parameter Algorithms for one-sided crossing minimization Revisited (2004)
Dujmovic, Vida, Fernau, Henning, Kaufmann, Michael
We exhibit a small problem kernel for the problem one-sided crossing minimization which plays an important role in graph drawing algorithms based on the Sugiyama layering approach. Moreover, we...
Really Straight Graph Drawings (2004)
Dujmovic, Vida, Suderman, Matthew, Wood, David R.
We study straight-line drawings of graphs with few segments and few slopes. Optimal results are obtained for all trees. Tight bounds are obtained for outerplanar graphs, 2-trees, and planar 3-trees....
Layouts of Graph Subdivisions (2004)
Dujmovic, Vida, Wood, David R.
A k-stack layout (respectively, k-queue layout) of a graph consists of a total order of the vertices, and a partition of the edges into k sets of non-crossing (non-nested) edges with respect to the...
Three-Dimensional Grid Drawings with Sub-quadratic Volume (2004)
Dujmovic, Vida, Wood, David R.
A three-dimensional grid drawing of a graph is a placement of the vertices at distinct points with integer coordinates, such that the straight line-segments representing the edges are pairwise...
Fixed Parameter Algorithms for one-sided crossing minimization Revisited (2004)
Dujmovic, Vida, Fernau, Henning, Kaufmann, Michael
We exhibit a small problem kernel for the problem one-sided crossing minimization which plays an important role in graph drawing algorithms based on the Sugiyama layering approach. Moreover, we...
Really Straight Graph Drawings (2004)
Dujmovic, Vida, Suderman, Matthew, Wood, David R.
We study straight-line drawings of graphs with few segments and few slopes. Optimal results are obtained for all trees. Tight bounds are obtained for outerplanar graphs, 2-trees, and planar 3-trees....
Layouts of Graph Subdivisions (2004)
Dujmovic, Vida, Wood, David R.
A k-stack layout (respectively, k-queue layout) of a graph consists of a total order of the vertices, and a partition of the edges into k sets of non-crossing (non-nested) edges with respect to the...
The Number of Lines Tangent to Arbitrary Convex Polyhedra in 3D (2004)
Brönnimann, Hervé, Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...
We prove that the lines tangent to four possibly intersecting polytopes in $R3$ with $n$ edges in total form $\Theta(n^2)$ connected components. In the generic case, each connected component is a...
The Number of Lines Tangent to Arbitrary Convex Polyhedra in 3D (2004)
Brönnimann, Hervé, Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...
We prove that the lines tangent to four possibly intersecting polytopes in $R3$ with $n$ edges in total form $\Theta(n^2)$ connected components. In the generic case, each connected component is a...
Three-Dimensional Grid Drawings with Sub-quadratic Volume (2004)
Dujmovic, Vida, Wood, David R.
A three-dimensional grid drawing of a graph is a placement of the vertices at distinct points with integer coordinates, such that the straight line-segments representing the edges are pairwise...
Fixed Parameter Algorithms for one-sided crossing minimization Revisited (2004)
Dujmovic, Vida, Fernau, Henning, Kaufmann, Michael
We exhibit a small problem kernel for the problem one-sided crossing minimization which plays an important role in graph drawing algorithms based on the Sugiyama layering approach. Moreover, we...
Really Straight Graph Drawings (2004)
Dujmovic, Vida, Suderman, Matthew, Wood, David R.
We study straight-line drawings of graphs with few segments and few slopes. Optimal results are obtained for all trees. Tight bounds are obtained for outerplanar graphs, 2-trees, and planar 3-trees....
Layouts of Graph Subdivisions (2004)
Dujmovic, Vida, Wood, David R.
A k-stack layout (respectively, k-queue layout) of a graph consists of a total order of the vertices, and a partition of the edges into k sets of non-crossing (non-nested) edges with respect to the...
A Fixed-Parameter Approach to Two-Layer Planarization (2004)
Vida Dujmovic, Michael Fellows, Michael Hallett, Matthew Kitching, Giuseppe Liotta, Catherine Mccartin, ...
A bipartite graph is biplanar if the vertices can be placed on two parallel lines (layers) in the plane such that there are no edge crossings when edges are drawn as line segments between the layers....
Layout of Graphs with Bounded Tree-Width (2004)
Vida Dujmovic, Pat Morin, David R. Wood
A queue 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...
Stacks, Queues and Tracks: Layouts of Graph Subdivisions (2004)
This paper studies stack, queue, and track layouts of graph subdivisions. It is known that every graph has a 3-stack subdivision. The best known upper bound on the number of division vertices per...
Really Straight Graph Drawings (2004)
Vida Dujmovic, Matthew Suderman, David R. Wood, Lower Bounds
We study straight-line drawings of graphs with few segments and few slopes. Optimal results are obtained for all trees. Tight bounds are obtained for outerplanar graphs, 2-trees, and planar 3-trees....
Track Layouts of Graphs (2004)
This paper presents the beginnings of a theory of track layouts. Our focus is on methods for the manipulation of track layouts, and the relationship between track layouts and other models of graph...
The expected number of 3D visibility events is linear (2003)
Th Emes Et, Vida Dujmovic, Sylvain Lazard, Olivier Devillers, Olivier Devillers, ...
apport de recherche
New Results in Graph Layout (2003)
A track layout of a graph consists of a vertex colouring, an edge colouring, and a total order of each vertex colour class such that between each pair of vertex colour classes, there is no...
The expected number of 3D visibility events is linear (2002)
Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Goaoc, Xavier, Lazard, Sylvain, Na, Hyeon-Suk, ...
In this paper, we show that, amongst n uniformly distributed unit balls in R^3, the expected number of maximal non-occluded line segments tangent to four balls is linear, considerably improving the...
Path-Width and Three-Dimensional Straight-Line Grid Drawings of Graphs (2002)
Dujmovic, Vida, Morin, Pat, Wood, David R.
We prove that every n-vertex graph G with path-width pw(G) has a three-dimensional straight-line grid drawing with O(pw(G)² *n) volume. Thus for graphs with bounded path-width the volume is O(n),...
An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization (2002)
Dujmovic, Vida, Whitesides, Sue
We give an \mathcal{O}(\phi^{k} \cdot n^2) algorithm for the 1-SIDED CROSSING MINIMIZATION problem, thus showing that the problem is Fixed Parameter Tractable. The constant $\phi$ in the running time...
A Fixed-Parameter Approach to Two-Layer Planarization (2002)
Dujmovic, Vida, Fellows, M., Hallett, M., Kitching, Matthew, Liotta, Giuseppe, McCartin, C., ...
A bipartite graph is biplanar if the vertices can be placed on two parallel lines (layers) in the plane such that there are no edge crossings when edges are drawn straight. The 2-LAYER PLANARIZATION...
Path-Width and Three-Dimensional Straight-Line Grid Drawings of Graphs (2002)
Dujmovic, Vida, Morin, Pat, Wood, David R.
We prove that every n-vertex graph G with path-width pw(G) has a three-dimensional straight-line grid drawing with O(pw(G)² *n) volume. Thus for graphs with bounded path-width the volume is O(n),...
An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization (2002)
Dujmovic, Vida, Whitesides, Sue
We give an \mathcal{O}(\phi^{k} \cdot n^2) algorithm for the 1-SIDED CROSSING MINIMIZATION problem, thus showing that the problem is Fixed Parameter Tractable. The constant $\phi$ in the running time...
A Fixed-Parameter Approach to Two-Layer Planarization (2002)
Dujmovic, Vida, Fellows, M., Hallett, M., Kitching, Matthew, Liotta, Giuseppe, McCartin, C., ...
A bipartite graph is biplanar if the vertices can be placed on two parallel lines (layers) in the plane such that there are no edge crossings when edges are drawn straight. The 2-LAYER PLANARIZATION...
The expected number of 3D visibility events is linear (2002)
Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Goaoc, Xavier, Lazard, Sylvain, Na, Hyeon-Suk, ...
In this paper, we show that, amongst n uniformly distributed unit balls in R^3, the expected number of maximal non-occluded line segments tangent to four balls is linear, considerably improving the...
The expected number of 3D visibility events is linear (2002)
Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Goaoc, Xavier, Lazard, Sylvain, Na, Hyeon-Suk, ...
In this paper, we show that, amongst n uniformly distributed unit balls in R^3, the expected number of maximal non-occluded line segments tangent to four balls is linear, considerably improving the...
Path-Width and Three-Dimensional Straight-Line Grid Drawings of Graphs (2002)
Dujmovic, Vida, Morin, Pat, Wood, David R.
We prove that every n-vertex graph G with path-width pw(G) has a three-dimensional straight-line grid drawing with O(pw(G)² *n) volume. Thus for graphs with bounded path-width the volume is O(n),...
An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization (2002)
Dujmovic, Vida, Whitesides, Sue
We give an \mathcal{O}(\phi^{k} \cdot n^2) algorithm for the 1-SIDED CROSSING MINIMIZATION problem, thus showing that the problem is Fixed Parameter Tractable. The constant $\phi$ in the running time...
A Fixed-Parameter Approach to Two-Layer Planarization (2002)
Dujmovic, Vida, Fellows, M., Hallett, M., Kitching, Matthew, Liotta, Giuseppe, McCartin, C., ...
A bipartite graph is biplanar if the vertices can be placed on two parallel lines (layers) in the plane such that there are no edge crossings when edges are drawn straight. The 2-LAYER PLANARIZATION...
Tree-partitions of k-trees with applications in graph layout (2002)
A tree-partition of a graph is a partition of its vertices into `bags' such that contracting each bag into a single vertex gives a forest (after deleting loops and replacing parallel edges by a...
Path-Width and Three-Dimensional Straight-Line Grid Drawings of Graphs (2002)
Vida Dujmovic, Pat Morin, David Wood
We prove that every n-vertex graph with path-width pw(G) a three-dimensional straight-line drawing with O(pw(G) u-g Thu graphs with bou58j path-width volu7 is O(n), follows that graphs with bou602...
Flat-State Connectivity of Linkages under Dihedral Motions (2002)
Greg Aloupis, Erik D. Demaine, Vida Dujmovic, Jeff Erickson, Stefan Langerman, Henk Meijer, ...
We explore which classes of linkages have the property that each pair of their at states|that is, their embeddings in R without self-intersection|can be connected by a continuous dihedral motion that...
Aichholzer, Oswin, Cortes, Carmen, Demaine, Erik D., Dujmovic, Vida, Erickson, Jeff, Meijer, Henk, ...
A flipturn is an operation that transforms a nonconvex simple polygon into another simple polygon, by rotating a concavity 180 degrees around the midpoint of its bounding convex hull edge. Joss and...
Efficient Topological Exploration (1999)
Ioannis M. Rekleitis, Vida Dujmovic
We consider the robot exploration of a planar graph-like world. The robot's goal is to build a complete map of its environment. The environment is modeled as an arbitrary undirected planar graph...