The maximum number of cliques in a graph embedded in a surface (2009)
Dujmović, Vida, Fijavž, Gašper, Joret, Gwenaël, Wood, David R.
This paper studies the following question: Given a surface $\Sigma$ and an integer $n$, what is the maximum number of cliques in an $n$-vertex graph embeddable in $\Sigma$? We characterise the...
Flipturning Polygons (Extended abstract) (2009)
Oswin Aichholzer, Carmen Cortés, Erik D. Demaine, Vida Dujmović, Jeff Erickson, Mark Overmars, ...
Figure 1. A flipturn. The pocket is bold (red), and its lid is dashed. A central problem in polymer physics and molecular biology is the reconfiguration of large molecules (modeled as polygons) such...
Every Large Point Set contains Many Collinear Points or an Empty Pentagon (2009)
Abel, Zachary, Ballinger, Brad, Bose, Prosenjit, Collette, Sébastien, Dujmović, Vida, Hurtado, Ferran, ...
We prove the following generalised empty pentagon theorem: for every integer $\ell \geq 2$, every sufficiently large set of points in the plane contains $\ell$ collinear points or an empty pentagon....
A CHARACTERIZATION OF THE DEGREE SEQUENCES OF 2-TREES (2009)
Prosenjit Bose, Vida Dujmović, Danny Krizanc, Stefan Langerman, Pat Morin
Abstract. We give an O(ϕ k · n 2) fixed parameter tractable algorithm for the 1-SIDED CROSSING MINIMIZA-TION problem. The constant ϕ in the running time is the golden ratio ϕ = (1 + √ 5)/2 ≈...
Curves in the Sand: Algorithmic Drawing (2008)
Mirela Damian, Erik D. Demaine, Martin L. Demaine, Vida Dujmović, Dania El-khechen, Robin Flatl, ...
Ethnomathematics is the study of mathematics in the works of art of various cultures [3, 4, 10, 14]. The concepts in this
DOI: 10.1007/s00453-005-1181-y A Fixed-Parameter Approach to 2-Layer Planarization ∗ (2008)
Vida Dujmović, Michael Fellows, Michael Hallett, Matthew Kitching, Catherine Mccartin, Naomi Nishimura, ...
Abstract. A bipartite graph is biplanar if the vertices can be placed on two parallel lines (layers) inthe plane such that there are no edge crossings when edges are drawn as line segments between...
Curves in the Sand: Algorithmic Drawing (2008)
Mirela Damian, Erik D. Demaine, Martin L. Demaine, Vida Dujmović, Dania El-khechen, Robin Flatl, ...
The field of ethnomathematics is the study of mathematics in the works of art of various cultures [2, 3, 9, 13]. The concepts
Induced Subgraphs of Bounded Degree and Bounded Treewidth ⋆ (2008)
Prosenjit Bose, Vida Dujmović, David R. Wood
Abstract. We prove that for all 0 ≤ t ≤ k and d ≥ 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...
ABSTRACT Improved Upper Bounds on the Crossing Number (2008)
Vida Dujmović, Bojan Mohar, David R. Wood
The crossing number of a graph is the minimum number of crossings in a drawing of the graph in the plane. Our main result is that every graph G that does not contain a fixed graph as a minor has...
Distinct Distances in Graph Drawings (2008)
Carmi, Paz, Dujmović, Vida, Morin, Pat, Wood, David R.
The \emph{distance-number} of a graph $G$ is the minimum number of distinct edge-lengths over all straight-line drawings of $G$ in the plane. This definition generalises many well-known concepts in...
A CHARACTERIZATION OF THE DEGREE SEQUENCES OF 2-TREES (2008)
Prosenjit Bose, Vida Dujmović, Danny Krizanc, Stefan Langerman, Pat Morin
Abstract Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint (2008)
Olivier Devillers, Vida Dujmović, Hazel Everett, Samuel Hornus, Sue Whitesides
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. 1
CONNECTIVITY–PRESERVING TRANSFORMATIONS OF BINARY IMAGES (2008)
Prosenjit Bose, Vida Dujmović, Ferran Hurtado, Pat Morin
ABSTRACT. A binary image I is Ba, Wb-connected, where a, b ∈ {4, 8}, if its foreground is a-connected and its background is b-connected. We consider a local modification of a Ba, Wb-connected image...
Curves in the Sand: Algorithmic Drawing (2008)
Mirela Damian, Erik D. Demaine, Martin L. Demaine, Vida Dujmović, Dania El-khechen, Robin Flatl, ...
Ethnomathematics is the study of mathematics in the works of art of various cultures [3, 4, 10, 14]. The concepts in this
CONNECTIVITY–PRESERVING TRANSFORMATIONS OF BINARY IMAGES (2008)
Prosenjit Bose, Vida Dujmović, Ferran Hurtado, Pat Morin
ABSTRACT. A binary image I is Ba, Wb-connected, where a, b ∈ {4, 8}, if its foreground is a-connected and its background is b-connected. We consider a local modification of a Ba, Wb-connected image...
Distribution-Sensitive Point Location in Convex Subdivisions ∗ Abstract (2008)
Sébastien Collette, Vida Dujmović, John Iacono, Stefan Langerman
A data structure is presented for point location in convex planar subdivisions when the distribution of queries is known in advance. The data structure has an expected query time that differs by only...
DISTRIBUTION-SENSITIVE POINT LOCATION IN CONVEX SUBDIVISIONS ∗ (2008)
Sébastien Collette, Stefan Langerman, Vida Dujmović, John Iacono, ...
ABSTRACT. A data structure is presented for point location in convex planar subdivisions when the distribution of queries is known in advance. The data structure has an expected query time that...
Distribution-Sensitive Point Location in Convex Subdivisions 1 (2008)
Sébastien Collette, Vida Dujmović, John Iacono, Stefan Langerman, Pat Morin
Abstract. A data structure is presented for point location in convex planar subdivisions when the distribution of queries is known in advance. If the optimal data structure in the linear decision...
Curves in the Sand: Algorithmic Drawing (2008)
Mirela Damian, Erik D. Demaine, Martin L. Demaine, Vida Dujmović, Dania El-khechen, Robin Flatl, ...
Ethnomathematics is the study of mathematics in the works of art of various cultures [3, 4, 10, 14]. The concepts in this
Contemporary Mathematics Three-Dimensional Grid Drawings with Sub-Quadratic Volume (2007)
Abstract. 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...
A polynomial bound for untangling geometric planar graphs (2007)
Prosenjit Bose, Vida Dujmović, Ferran Hurtado, Stefan Langerman, Pat Morin, David R. Wood
ABSTRACT. 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...
Improved Upper Bounds on the Crossing Number (2007)
Vida Dujmović, Ken-ichi Kawarabayashi, Bojan Mohar, David R. Wood
The crossing number of a graph is the minimum number of crossings in a drawing of the graph in the plane. Our main result is that every graph G that excludes a fixed graph as a minor has crossing...
A Characterization of the Degree Sequences of 2-Trees (2006)
Bose, Prosenjit, Dujmović, Vida, Krizanc, Danny, Langerman, Stefan, Morin, Pat, Wood, David R., ...
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\v{i}s a 2-tree. A characterization of the degree sequences of 2-trees is given. This...
Lines and free line segments tangent to arbitrary three-dimensional convex polyhedra (2006)
Olivier Devillers, Vida Dujmović, Hazel Everett, Marc Glisse, Xavier Goaoc, Sylvain Lazard, ...
SUE WHITESIDES∗ ∗ Abstract. 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...
A CHARACTERIZATION OF THE DEGREE SEQUENCES OF 2-TREES (2006)
Prosenjit Bose, Vida Dujmović, Danny Krizanc, Stefan Langerman, Pat Morin
ABSTRACT. A graph G is a 2-tree if G = K3, or G has a vertex v of degree 2, whose neighbours are adjacent, and G\v is a 2-tree. A characterization of the degree sequences of 2-trees is given. This...
Lines and free line segments tangent to arbitrary three-dimensional convex polyhedra (2006)
Hervé Brönnimann, Olivier Devillers, Vida Dujmović, Hazel Everett, Xavier Goaoc, Sylvain Lazard, ...
Abstract. 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...
Upward Three-Dimensional Grid Drawings of Graphs (2005)
Dujmović, Vida, Wood, David R.
A \emph{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 do not...
GRAPH DRAWINGS WITH FEW SLOPES ∗ Dedicated to Godfried Toussaint on his 60th birthday. (2005)
Vida Dujmović, Matthew Suderman, David R. Wood
The slope-number of a graph G is the minimum number of distinct edge slopes in a straight-line drawing of G in the plane. We prove that for ∆ ≥ 5 and all large n, there is a ∆-regular n-vertex...
Vida Dujmović, David R. Wood, Vida Dujmović, David R. Wood
Abstract 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...
Drawings of planar graphs with few slopes and segments (2005)
Vida Dujmović, Matthew Suderman, David R. Wood
We study straight-line drawings of planar 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...
Really straight drawings II: Non-planar graphs (2005)
Vida Dujmović, Matthew Suderman, David R. Wood
We study straight-line drawings of non-planar graphs with few slopes. Interval graphs, co-comparability graphs and AT-free graphs are shown to have have drawings in which the number of slopes is...
Really straight drawings I: Planar graphs (2005)
Vida Dujmović, Matthew Suderman, David R. Wood
We study straight-line drawings of planar 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...
Upward three-dimensional grid drawings of graphs. arXiv.org math.CO/0510051 (2005)
Abstract. 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 do not...
Stacks, Queues and Tracks: Layouts of Graph Subdivisions (2005)
A k-stack layout (respectively, k-queuelayout) 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)
Abstract. 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...
Fixed parameter algorithms for one-sided crossing minimization revisited (2004)
Vida Dujmović, Henning Fernau, Michael Kaufmann
We exhibit a small problem kernel for the one-sided crossing minimization problem. This problem plays an important role in graph drawing algorithms based on the Sugiyama layering approach. Moreover,...
Induced Subgraphs of Bounded Degree and Bounded Treewidth (2004)
Prosenjit Bose, Vida Dujmović, David R. Wood
We prove that for all 0 ≤ t ≤ k and d ≥ 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 degree at...
Fixed parameter algorithms for one-sided crossing minimization revisited (2004)
Vida Dujmović, Henning Fernau, Michael Kaufmann
Abstract. We exhibit a small problem kernel for the problem onesided crossing minimization which plays an important role in graph drawing algorithms based on the Sugiyama layering approach. Moreover,...
On Linear Layouts of Graphs (2004)
In a total order of the vertices of a graph, two edges with no endpoint in common can be crossing, nested, or disjoint. A k-stack (respectively, k-queue, k-arch) layout of a graph consists of a total...
Track Layouts of Graphs (2004)
Vida Dujmović, Attila Pór, David R. Wood
A (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...
Stacks, Queues and Tracks: Layouts of Graph Subdivisions † (2003)
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...
On linear layouts of graphs (2003)
In a total order of the vertices of a graph, two edges with no endpoint in common can be crossing, nested, or disjoint. A k-stack (respectively, k-queue, k-arch) layout of a graph consists of a total...
On linear layouts of graphs (2003)
Vida Dujmović, Attila Pór, David R. Wood
A (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...
Stacks, Queues and Tracks: Layouts of Graph Subdivisions † (2003)
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...
Flat-state connectivity of linkages under dihedral motions (2002)
Greg Aloupis, Erik D. Demaine, Vida Dujmović, Jeff Erickson, Stefan Langerman, Henk Meijer, ...
Abstract. We explore which classes of linkages have the property that each pair of their flat states—that is, their embeddings in R 2 without self-intersection—can be connected by a continuous...
Tree-partitions of k-trees with applications in graph layout (2002)
Abstract. 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. It is proved that every k-tree has a...
Layout of graphs with bounded tree-width (2002)
Vida Dujmović, Pat Morin, R. Wood
Abstract. 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...
Path-width and three-dimensional straight-line grid drawings of graphs (2002)
Vida Dujmović, Pat Morin, David R. Wood
Abstract. We prove that every-vertex graph with pathwidth has a three-dimensional straight-line grid drawing with volume. Thus for graphs with bounded pathwidth the volume is, and it follows that for...
A fixed-parameter approach to two-layer planarization (2001)
Vida Dujmović, Michael Fellows, Michael Hallett, Matthew Kitching, Catherine Mccartin, Naomi Nishimura, ...
1 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...
A fixed-parameter approach to two-layer planarization (2001)
Vida Dujmović, Michael Fellows, Michael Hallett, Matthew Kitching, Catherine Mccartin, Naomi Nishimura, ...
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....
Algorithmic aspects of planar map validation by a mobile agent (2000)
In this thesis we present an optimal linear time algorithm for validating the correctness of a map by an active agent (such as a person or a mobile robot). The robot is given a possibly incorrect map...
Algorithmic aspects of planar map validation by a mobile agent (2000)
In this thesis we present an optimal linear time algorithm for validating the correctness of a map by an active agent (such as a person or a mobile robot). The robot is given a possibly incorrect map...
Efficient topological exploration (1999)
Ioannis M. Rekleitis, Vida Dujmović, Gregory Dudek
We consider the robot exploration of a planar graphlike world. The robot’s goal is to build a complete map of its environment. The environment is modeled as an arbitrary undirected planar graph...
Efficient topological exploration (1999)
Ioannis M. Rekleitis, Vida Dujmović, Gregory Dudek
We consider the robot exploration of a planar graphlike world. The robot’s goal is to build a complete map of its environment. The environment is modeled as an arbitrary undirected planar graph...