Psychological Assessment of Fatigue in a Medical Setting, (9999)
Powell,John B., Kroenke,Kurt K., Wood,David R., Mangelsdorff,A. D.
Fatigue is the seventh most common complaint in ambulatory medical care. Little research has been done, however, with the few available studies being retrospective and uncontrolled. The present study...
Fabila-Monroy, Ruy, Flores-Peñaloza, David, Huemer, Clemens, Hurtado, Ferran, Urrutia, Jorge, Wood, David R.
For a graph $G$ and integer $k\geq1$, we define the token graph $F_k(G)$ to be the graph with vertex set all $k$-subsets of $V(G)$, where two vertices are adjacent in $F_k(G)$ whenever their...
Irreducible Triangulations are Small (2009)
Joret, Gwenaël, Wood, David R.
A triangulation of a surface is \emph{irreducible} if there is no edge whose contraction produces another triangulation of the surface. We prove that every irreducible triangulation of a surface with...
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...
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....
Characterisations and Examples of Graph Classes with Bounded Expansion (2009)
Nešetřil, Jaroslav, De Mendez, Patrice Ossona, Wood, David R.
Classes with bounded expansion, which generalise classes that exclude a topological minor, have recently been introduced by Ne\v{s}et\v{r}il and Ossona de Mendez. These classes are defined by the...
The Distance Geometry of Deep Rhythms and Scales (2008)
Erik D. Demaine, Francisco Gomez-martin, Henk Meijer, Perouz Taslakian, Godfried T. Toussaint, Terry Winograd, ...
Abstract We characterize which sets of k points chosen from n points spaced evenly around a circle have the property that, for each i = 1, 2,..., k − 1, there is a nonzero distance along the circle...
Graph Minors and Minimum Degree (2008)
Fijavž, Gašper, Wood, David R.
Let $\mathcal{D}_k$ be the class of graphs for which every minor has minimum degree at most $k$. Then $\mathcal{D}_k$ is closed under taking minors. By the Robertson-Seymour graph minor theorem,...
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...
A Fixed-Parameter Approach to Two-Layer (2008)
V. Dujmović, M. Fellows, M. Hallett, M. Kitching, C. Mccartin, N. Nishimura, ...
Abstract. 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...
Contractibility and the Hadwiger Conjecture (2008)
Consider the following relaxation of the Hadwiger Conjecture: For each $t$ there exists $N_t$ such that every graph with no $K_t$-minor admits a vertex partition into $\ceil{\alpha t+\beta}$ parts,...
Polynomial treewidth forces a large grid-like-minor (2008)
Reed, Bruce A., Wood, David R.
Robertson and Seymour proved that every graph with sufficiently large treewidth contains a large grid minor. However, the best known bound on the treewidth that forces an $\ell\times\ell$ grid minor...
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 NOTE ON COLOURING THE PLANE GRID ∗ (2008)
Let n be a positive integer. The n × n grid is the set of points in the plane {(x, y) : 1 ≤ x, y ≤ n}. Let k(n) denote the minimum number of colours in a colouring of the points of the n × n...
On the Chromatic Numbers of some Flip Graphs (2008)
Ruy Fabila-monroy, David Flores-peñaloza, Clemens Huemer, Ferran Hurtado, Jorge Urrutia, David R. Wood
This paper studies the chromatic number of the following four flip graphs (under suitable definitions of a flip): • the flip graph of perfect matchings of a complete graph of even order, • the...
Grid drawings of k-colourable graphs (2008)
www.elsevier.com/locate/comgeo It is proved that every k-colourable graph on n vertices has a grid drawing with O(kn) area, and that this bound is best possible. This result can be viewed as a...
DOI: 10.1007/s00453-006-0158-9 No-Three-in-Line-in-3D 1 (2008)
Abstract. The no-three-in-line problem, introduced by Dudeney in 1917, asks for the maximum number of points in the n × n grid with no three points collinear. Erdős proved that the answer is...
Bounded-degree graphs have arbitrarily large geometric thickness (2008)
The geometric thickness of a graph G is the minimum integer k such that there is a straight line drawing of G with its edge set partitioned into k plane subgraphs. Eppstein [Separating thickness from...
1 Introduction Cost-Optimal Quadtrees for Ray Shooting ∗ (2008)
Hervé Brönnimann, Marc Glisse, David R. Wood
Given a set S of objects, called a scene, the rayshooting problem asks, given a ray, what is the first
Fast separation in a graph with an excluded minor † (2008)
Let G be an n-vertex m-edge graph with weighted vertices. A pair of vertex sets A, B ⊆ V (G) is a 2
Lower bounds for the number of bends in three-dimensional orthogonal graph drawings (2008)
This paper presents the first non-trivial lower bounds for the total number of bends in 3-D orthogonal graph drawings with vertices represented by points. In particular, we prove lower bounds for the...
Therese Biedl, Torsten Thiele, David R. Wood, T. Biedl, T. Thiele, D. R. Wood, ...
Abstract An orthogonal drawing of a graph is an embedding of the graph in the rectangular grid, with vertices represented by axis-aligned boxes, and edges represented by paths in the grid which only...
The foldings of a connected graph $G$ are defined as follows. First, $G$ is a folding of itself. Let $G'$ be a graph obtained from $G$ by identifying two vertices at distance 2 in $G$. Then every...
VERTEX PARTITIONS OF CHORDAL GRAPHS (2008)
Abstract. A k-tree is a chordal graph with no (k + 2)-clique. An ℓ-treepartition of a graph G is a vertex partition of G into ‘bags’, such that con-tracting each bag to a single vertex gives an...
vol., no., pp. – () The Maximum Number of Edges in a Three-Dimensional Grid-Drawing ∗ (2008)
Prosenjit Bose, Jurek Czyzowicz, Gatineau Québec Canada, Pat Morin, David R. Wood
An exact formula is given for the maximum number of edges in a graph that admits a three-dimensional grid-drawing contained in a given bound-ing box. The first universal lower bound on the volume of...
Bounded-Degree Graphs have Arbitrarily Large Queue-Number (2008)
It is proved that there exist graphs of bounded degree with arbitrarily large queue-number. In particular, for all Δ ≥ 3 and for all sufficiently large n, there is a simple Δ-regular n-vertex...
Token Distribution on Tree-Connected Architectures (2007)
Michael E. Houle, Antonios Symvonis, David R. Wood
Load balancing on a multi-processor system involves redistributing tasks among processors so that each processor has roughly the same amount of work to perform. The token-distribution problem is a...
Some of these results were presented at the Australasian Workshop on Combinatorial Algorithms (2007)
A 3-D orthogonal drawing of graph with maximum degree at most six positions the vertices at grid-points in the 3-D orthogonal grid, and routes edges along grid-lines such that edge routes only...
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...
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...
Let n be a positive integer. The n n grid is the set of points in the plane f(x; y) : 1 x; y ng. Let k(n) denote the minimum number of colours in a colouring of the points of the n n grid such that...
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...
Therese Biedl, Timothy Chan, Yashar Ganjali, Mohammadtaghi Hajiaghayi, David R. Wood
We consider the problem of determining a balanced ordering of the vertices of a graph; that is, the neighbors of each vertex v are as evenly distributed to the left and right of v as possible. This...
Star Colourings of Subdivisions (2007)
Let G be a graph with chromatic number (G) and maximum degree (G). A star colouring of G is a function that assigns a colour to each vertex such that adjacent vertices receive distinct colours, and...
www.elsevier.com/locate/tcs Optimal three-dimensional orthogonal graph drawing in the general position model
Jurek Czyzowicz, Pat Morin, David R. Wood
An exact formula is given for the maximum number of edges in a graph that admits a three-dimensional grid-drawing contained in a given bounding box. A three-dimensional (straight-line) grid-drawing...
Grid drawings of k-colourable graphs (2007)
It is proved that every k-colourable graph on n vertices has a grid drawing with O(kn) area, and that this bound is best possible. This result can be viewed as a generalisation of the...
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...
Book Embeddings, David R. Wood
A book embedding of a graph consists of a linear ordering of the vertices along a line in 3-space (the spine), and an assignment of edges to half-planes with the spine as boundary (the pages), so...
Therese Biedl, Torsten Thiele, David R. Wood
Abstract An orthogonal drawing of a graph is an embedding of the graph in the rectangular grid, with vertices represented by axis-aligned boxes, and edges represented by paths in the grid which only...
Geometric thickness in a grid of linear area (2007)
Let G = (V; E) be a connected graph with n = jV j vertices, m = jEj edges, maximum degree , and genus . The thickness of G, denoted by (G), is the minimum number of subgraphs in a partition of the...
Some of these results were presented at the Australasian Workshop on Combinatorial Algorithms (2007)
A 3-D orthogonal drawing of graph with maximum degree at most six positions the vertices at grid-points in the 3-D orthogonal grid, and routes edges along grid-lines such that edge routes only...
Geometric thickness in a grid (2007)
The geometric thickness of a graph is the minimum number of layers such that the graph can be drawn in the plane with edges as straight-line segments, and with each edge assigned to a layer so that...
Therese Biedl, Timothy Chan, Yashar Ganjali, Mohammadtaghi Hajiaghayi, David R. Wood
We consider the problem of determining a balanced ordering of the vertices of a graph; that is, the neighbors of each vertex v are as evenly distributed to the left and right of v as possible. This...
On Pseudo Vertex-Magic and Edge-Magic Total-Labellings (2007)
Abstract. To date the study of graph labellings has focused on nding classes of graphs which admit a particular type of labelling. Here we consider variations of the well-known edge-magic and...
Bounded Degree Acyclic Decompositions of Digraphs (2007)
1 An acyclic decomposition of a digraph is a partition of the edges into acyclic subgraphs. Trivially every digraph has an acyclic decomposition into two subgraphs. We prove that for every integer s...
Re nement of Three-Dimensional Orthogonal Graph Drawings (2007)
Antonios Symvonis, David R. Wood
Abstract. In this paper we introduce a number of techniques for the re nement of three-dimensional orthogonal drawings of maximum degree six graphs. We have implemented several existing algorithms...
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...
Cost-Optimal Quadtrees for Ray Shooting Herve Bronnimann y (2007)
Given a set S of objects, called a scene, the rayshooting problem asks, given a ray, what is the rst object in S intersected by this ray. A popular approach
Light Edges in Degree-Constrained Graphs Prosenjit Bose z (2007)
A graph whose average degree is less than twice the minimum degree is called degree-constrained. An edge of a graph with bounded degree end-points is said to be light. The primary result of this...
On Pseudo Vertex-Magic and Edge-Magic Total-Labellings (2007)
To date the study of graph labellings has focused on nding classes of graphs which admit a particular type of labelling. Here we consider variations of the well-known edge-magic and vertex-magic...
Light Edges in Degree-Constrained Graphs (2007)
Prosenjit Bose Michiel, Michiel Smid, David R. Wood
Let denote the average degree, and denote the minimum degree of a graph.
Cost-Optimal Quadtrees for Ray Shooting (2007)
Hervé Brönnimann, Marc Glisse, David R. Wood
this paper, the only objects we consider are simplices (points and segments inside the unit square [0; 1] in R , or points, segments and triangles inside the unit cube [0; 1] in R ). We denote the...
Abstract. A 3-dimensional orthogonal drawing of a graph with maximum degree at most 6, positions the vertices at grid-points in the 3-dimensional orthogonal grid, and routes edges along grid-lines...
The no-three-in-line problem, introduced by Dudeney in 1917, asks for the maximum number of points in the nn grid with no three points collinear. In 1951, Erdos proved that the answer is (n). We...
Clique Minors in Cartesian Products of Graphs (2007)
A "clique minor" in a graph G can be thought of as a set of connected subgraphs in G that are pairwise disjoint and pairwise adjacent. The "Hadwiger number" h(G) is the maximum cardinality of a...
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...
Compatible Geometric Matchings (2007)
Aichholzer, Oswin, Bereg, Sergey, Dumitrescu, Adrian, García, Alfredo, Huemer, Clemens, Hurtado, Ferran, ...
This paper studies non-crossing geometric perfect matchings. Two such perfect matchings are \emph{compatible} if they have the same vertex set and their union is also non-crossing. Our first result...
The Distance Geometry of Music (2007)
Demaine, Erik D., Gomez-Martin, Francisco, Meijer, Henk, Rappaport, David, Taslakian, Perouz, Toussaint, Godfried T., ...
We demonstrate relationships between the classic Euclidean algorithm and many other fields of study, particularly in the context of music and distance geometry. Specifically, we show how the...
Extremal Graph Theory for Metric Dimension and Diameter (2007)
Hernando, Carmen, Mora, Merce, Pelayo, Ignacio M., Seara, Carlos, Wood, David R.
A set of vertices $S$ \emph{resolves} a connected graph $G$ if every vertex is uniquely determined by its vector of distances to the vertices in $S$. The \emph{metric dimension} of $G$ is the minimum...
Planar Decompositions and the Crossing Number of Graphs with an Excluded Minor (2007)
Wood, David R., Telle, Jan Arne
Tree decompositions of graphs are of fundamental importance in structural and algorithmic graph theory. Planar decompositions generalise tree decompositions by allowing an arbitrary planar graph to...
Planar Decompositions and the Crossing Number of Graphs with an Excluded Minor (2007)
Wood, David R., Telle, Jan Arne
Tree decompositions of graphs are of fundamental importance in structural and algorithmic graph theory. Planar decompositions generalise tree decompositions by allowing an arbitrary planar graph to...
Compatible Geometric Matchings (2007)
Oswin Aichholzer, Sergey Bereg, Adrian Dumitrescu, Alfredo García, Clemens Huemer, Ferran Hurtado, ...
Abstract: This paper studies non-crossing geometric perfect matchings. Two such perfect matchings are compatible if they have the same vertex set and their union is also non-crossing. Our first...
Planar decompositions and the crossing number of graphs with an excluded minor (2007)
Arne Telle, David R. Wood, David R. Wood, Jan Arne Telle
ABSTRACT. Tree decompositions of graphs are of fundamental importance in structural and algorithmic graph theory. Planar decompositions generalise tree decompositions by allowing an arbitrary planar...
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...
Independent Sets in Graphs with an Excluded Clique Minor (2007)
Let G be a graph with n vertices, with independence number α, and with no K t+1-minor for some t ≥ 5. It is proved that (2α - 1)(2t - 5) ≥ 2n - 5.
On the complexity of the balanced vertex ordering problem (2007)
Jan Kara, Jan Kratochvil, David R. Wood
We consider the problem of finding a balanced ordering of the vertices of a graph. More precisely, we want to minimise the sum, taken over all vertices v, of the difference between the number of...
On the Oriented Chromatic Number of Dense Graphs (2006)
Let $G$ be a graph with $n$ vertices, $m$ edges, average degree $\delta$, and maximum degree $\Delta$. The "oriented chromatic number" of $G$ is the maximum, taken over all orientations of $G$, of...
The Minor Crossing Number of Graphs with an Excluded Minor (2006)
Bokal, Drago, Fijavž, Gašper, Wood, David R.
The "minor crossing number" of a graph $G$ is the minimum crossing number of a graph that contains $G$ as a minor. It is proved that for every graph $H$ there is a constant $c$, such that every graph...
Graph Drawings with Few Slopes (2006)
Dujmovic', Vida, Suderman, Matthew, Wood, David R.
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 $\Delta\geq5$ and all large $n$, there is a...
Drawings of Planar Graphs with Few Slopes and Segments (2006)
Dujmovic', Vida, Eppstein, David, Suderman, Matthew, Wood, David R.
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...
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...
Planar Decompositions and the Crossing Number of Graphs with an Excluded Minor (2006)
Wood, David R., Telle, Jan Arne
Tree decompositions of graphs are of fundamental importance in structural and algorithmic graph theory. Planar decompositions generalise tree decompositions by allowing an arbitrary planar graph to...
On Tree-Partition-Width (2006)
A \emph{tree-partition} of a graph $G$ is a proper partition of its vertex set into `bags', such that identifying the vertices in each bag produces a forest. The \emph{tree-partition-width} of $G$ is...
On the maximum number of cliques in a graph (2006)
A \emph{clique} is a set of pairwise adjacent vertices in a graph. We determine the maximum number of cliques in a graph for the following graph classes: (1) graphs with $n$ vertices and $m$ edges;...
Bounded-Degree Graphs have Arbitrarily Large Queue-Number (2006)
It is proved that there exist graphs of bounded degree with arbitrarily large queue-number. In particular, for all $\Delta\geq3$ and for all sufficiently large $n$, there is a simple $\Delta$-regular...
Independent Sets in Graphs with an Excluded Clique Minor (2006)
Let $G$ be a graph with $n$ vertices, with independence number $\alpha$, and with with no $K_{t+1}$-minor for some $t\geq5$. It is proved that $(2\alpha-1)(2t-5)\geq2n-5$.
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...
Partitions of complete geometric graphs into plane trees (2006)
Prosenjit Bose, Ferran Hurtado, Eduardo Rivera-campo, David R. Wood
Consider the open problem: does every complete geometric graph K 2n have a partition of its edge set into n plane spanning trees? We approach this problem from three directions. First, we study the...
Partitions of complete geometric graphs into plane trees (2006)
Prosenjit Bose, Ferran Hurtado, Eduardo Rivera-campo, Iztapalapa México, David R. Wood
Consider the following question: does every complete geometric graph K2n have a partition of its edge set into n plane spanning trees? We approach this problem from three directions. First, we study...
A note on tree-partition-width (2006)
Abstract. A tree-partition of a graph G is a proper partition of its vertex set into ‘bags’, such that identifying the vertices in each bag produces a forest. The tree-partition-width of G is the...
The Minor Crossing Number of Graphs with an Excluded Minor (2006)
Mathematics Subject Classifications: 05C62 (graph representations), 05C10 (topological graph theory), 05C83 (graph minors) The minor crossing number of a graph G is the minimum crossing number of a...
Partitions of complete geometric graphs into plane trees (2006)
Prosenjit Bose, Ferran Hurtado, Eduardo Rivera-campo, David R. Wood, Politècnica De Catalunya
Consider the open problem: does every complete geometric graph K2n have a partition of its edge set into n plane spanning trees? We approach this problem from three directions. First, we study the...
A linear upper bound on the rectilinear crossing number (2005)
It is proved that the rectilinear crossing number of every graph with bounded tree-width and bounded degree is linear in the number of vertices. **** This paper has been withdrawn by the author. ****...
Colourings of the Cartesian Product of Graphs and Multiplicative Sidon Sets (2005)
Let $F$ be a family of connected bipartite graphs, each with at least three vertices. A proper vertex colouring of a graph $G$ with no bichromatic subgraph in $F$ is $\F$-free. The $F$-free chromatic...
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...
Notes on Nonrepetitive Graph Colouring (2005)
A vertex colouring of a graph is \emph{nonrepetitive on paths} if there is no path $v_1,v_2,...,v_{2t}$ such that v_i and v_{t+i} receive the same colour for all i=1,2,...,t. We determine the maximum...
Simultaneous Diagonal Flips in Plane Triangulations (2005)
Bose, Prosenjit, Czyzowicz, Jurek, Gao, Zhicheng, Morin, Pat, Wood, David R.
Simultaneous diagonal flips in plane triangulations are investigated. It is proved that every $n$-vertex triangulation with at least six vertices has a simultaneous flip into a 4-connected...
Drawing a Graph in a Hypercube (2005)
A $d$-dimensional hypercube drawing of a graph represents the vertices by distinct points in $\{0,1\}^d$, such that the line-segments representing the edges do not cross. We study lower and upper...
Bounded-Degree Graphs have Arbitrarily Large Geometric Thickness (2005)
Barat, Janos, Matousek, Jiri, Wood, David R.
The geometric thickness of a graph G is the minimum integer k such that there is a straight line drawing of G with its edge set partitioned into k plane subgraphs. Eppstein [Separating thickness from...
Bounded-Degree Graphs have Arbitrarily Large Geometric Thickness (2005)
Matousek, Jirí, Barát, János, Wood, David R.
The geometric thickness of a graph G is the minimum integer k such that there is a straight line drawing of G with its edge set partitioned into k plane subgraphs. Eppstein [Separating thickness from...
Bounded-Degree Graphs have Arbitrarily Large Geometric Thickness (2005)
Matousek, Jirí, Barát, János, Wood, David R.
The geometric thickness of a graph G is the minimum integer k such that there is a straight line drawing of G with its edge set partitioned into k plane subgraphs. Eppstein [Separating thickness from...
Bounded-Degree Graphs have Arbitrarily Large Geometric Thickness (2005)
Matousek, Jirí, Barát, János, Wood, David R.
The geometric thickness of a graph G is the minimum integer k such that there is a straight line drawing of G with its edge set partitioned into k plane subgraphs. Eppstein [Separating thickness from...
On the Metric Dimension of Cartesian Products of Graphs (2005)
Cáceres, José, Hernando, Carmen, Mora, Mercé, Pelayo, Ignacio M., Puertas, María L., Seara, Carlos, ...
A set S of vertices in a graph G resolves G if every vertex is uniquely determined by its vector of distances to the vertices in S. The metric dimension of G is the minimum cardinality of a resolving...
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...
A Simple Proof of the F{\'a}ry-Wagner Theorem (2005)
We give a simple proof of the following fundamental result independently due to Fary (1948) and Wagner (1936): Every plane graph has a drawing in which every edge is straight.
Graph Treewidth and Geometric Thickness Parameters (2005)
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...
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...
Acyclic, star and oriented colourings of graph subdivisions (2005)
Let G be a graph with chromatic number χ(G). A vertex colouring of G is acyclic if each bichromatic subgraph is a forest. A star colouring of G is an acyclic colouring in which each bichromatic...
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...
On the complexity of the balanced vertex ordering problem (2005)
Jan Kára, Jan Kratochvíl, David R. Wood
Abstract. We consider the problem of finding a balanced ordering of the vertices of a graph. More precisely, we want to minimise the sum, taken over all vertices v, of the difference between the...
Queue Layouts of Graph Products and (2005)
A k-queue layout of a graph G consists of a linear order σ of V (G), and a partition of E(G) into k sets, each of which contains no two edges that are nested in σ. This paper studies queue layouts...
Queue Layouts of Graph Products and Powers (2005)
A k-queue layout of a graph G consists of a linear order σ of V(G), and a partition of E(G) into k sets, each of which contains no two edges that are nested in σ. This paper studies queue layouts...
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...
Acyclic, Star and Oriented Colourings of Graph Subdivisions (2005)
Let G be a graph with chromatic number χ(G). A vertex colouring of G is acyclic if each bichromatic subgraph is a forest. A star colouring of G is an acyclic colouring in which each bichromatic...
Vertex Partitions of Chordal Graphs (2004)
A \emph{$k$-tree} is a chordal graph with no $(k+2)$-clique. An \emph{$\ell$-tree-partition} of a graph $G$ is a vertex partition of $G$ into `bags', such that contracting each bag to a single vertex...
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"...
Characterisations of Intersection Graphs by Vertex Orderings (2004)
Characterisations of interval graphs, comparability graphs, co-comparability graphs, permutation graphs, and split graphs in terms of linear orderings of the vertex set are presented. As an...
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...
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 no-three-in-line problem, introduced by Dudeney in 1917, asks for the maximum number of points in the n × n grid with no three points collinear. In 1951, Erdös proved that the answer is \Theta...
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...
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 no-three-in-line problem, introduced by Dudeney in 1917, asks for the maximum number of points in the n × n grid with no three points collinear. In 1951, Erdös proved that the answer is \Theta...
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...
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 no-three-in-line problem, introduced by Dudeney in 1917, asks for the maximum number of points in the n × n grid with no three points collinear. In 1951, Erdös proved that the answer is \Theta...
Light edges in degree-constrained graphs (2004)
Prosenjit Bose, Michiel Smid, David R. Wood
Let denote the average degree, and denote the minimum degree of a graph. An edge is light if both its endpoints have degree bounded by a constant depending only on and. A graph is degree-constrained...
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...
Three-Dimensional 1-Bend Graph Drawings (2004)
We consider three-dimensional grid-drawings of graphs with at most one bend per edge. Under the additional requirement that the vertices be collinear, we prove that the minimum volume of such a...
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...
Light edges in degree-constrained graphs (2004)
Prosenjit Bose, Michiel Smid, David R. Wood
A graph whose average degree is less than twice the minimum degree is called degree-constrained. An edge of a graph with bounded degree end-points is said to be light. The primary result of this...
Light edges in degree-constrained graphs (2004)
Prosenjit Bose, Michiel Smid, David R. Wood
A graph whose average degree is less than twice the minimum degree is called degree-constrained. An edge of a graph with bounded degree end-points is said to be light. The primary result of this...
Bounded Degree Acyclic Decompositions of Digraphs (2004)
An acyclic decomN-56NgE of a digraph is a partition of the edges into acyclic subgraphs. Trivially every digraph has an acyclicdecomgNj/$Ng into two subgraphs. It is proved that for every integer sX2...
Characterisations of Intersection Graphs by Vertex Orderings (2004)
Characterisations of interval graphs, comparability graphs, co-comparability graphs, permutation graphs, and split graphs in terms of linear orderings of the vertex set are presented. As an...
Balanced Vertex-Orderings of Graphs (2004)
Therese Biedl, Timothy Chan, Yashar Ganjali, Mohammadtaghi Hajiaghayi, David R. Wood
In this paper we consider the problem of determining a balanced ordering of the vertices of a graph; that is, the neighbors of each vertex v are as evenly distributed to the left and right of v as...
Three-Dimensional Orthogonal Graph Drawing with Optimal Volume (2004)
Therese Biedl, Torsten Thiele, David R. Wood
An orthogonal drawing of a graph is an embedding of the graph in the rectangular grid, with vertices represented by axis-aligned boxes, and edges represented by paths in the grid that only possibly...
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....
Light Edges in Degree-Constrained Graphs (2004)
Prosenjit Bose Michiel, Michiel Smid, David R. Wood
A graph whose average degree is less than twice the minimum degree is called degree-constrained. An edge of a graph with bounded degree end-points is said to be light. The primary result of this...
Three-Dimensional 1-Bend Graph Drawings (2004)
We consider three-dimensional grid-drawings of graphs with at most one bend per edge. Under the additional requirement that the vertices be collinear, we prove that the minimum volume of such a...
On the Chromatic Number of the Visibility Graph of a Set of Points in the Plane* (2004)
Abstract The visibility graph V(P) of a point set P ` R2 has vertex set P, such that two points v, w 2 P are adjacent whenever there is no other point in P on the line segment between v and w. We...
Drawing a graph in a hypercube (2004)
A d-dimensional hypercube drawing of a graph represents the vertices by distinct points in {0, 1} d, such that the line-segments representing the edges do not cross. We study lower and upper bounds...
Three-Dimensional 1-Bend Graph Drawings (2004)
We consider three-dimensional grid-drawings of graphs with at most one bend per edge. Under the additional requirement that the vertices be collinear, we prove that the minimum volume of such a...
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...
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...
The maximum number of edges in a three-dimensional grid-drawing (2003)
Prosenjit Bose, Jurek Czyzowicz, Pat Morin, David R. Wood
An exact formula is given for the maximum number of edges in a graph that admits a three-dimensional grid-drawing contained in a given bounding box. A three-dimensional (straight-line) grid-drawing...
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...
The maximum number of edges in a three-dimensional grid-drawing (2003)
Jurek Czyzowicz, Pat Morin, David R. Wood
An exact formula is given for the maximum number of edges in a graph that admits a three-dimensional grid-drawing contained in a given bounding box. A three-dimensional (straight-line) grid-drawing...
The maximum number of edges in a three-dimensional grid-drawing (2003)
Prosenjit Bose, Jurek Czyzowicz, Pat Morin, David R. Wood
vol., no., pp.-- ()
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 Maximum Number of Edges in a Three-Dimensional Grid-Drawing (2003)
Prosenjit Bose, Jurek Czyzowicz, Pat Morin, David R. Wood
An exact formula is given for the maximum number of edges in a graph that admits a three-dimensional grid-drawing contained in a given bounding box. The first universal lower bound on the volume of...
Simultaneous Diagonal Flips in Plane (2003)
Prosenjit Bose, Jurek Czyzowicz, Zhicheng Gao, Pat Morin, David R. Wood
† Research partially completed at Carleton University and McGill University
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...
The maximum number of edges in a three-dimensional grid-drawing (2003)
Prosenjit Bose, Jurek Czyzowicz, Pat Morin, David R. Wood
An exact formula is given for the maximum number of edges in a graph that admits a three-dimensional grid-drawing contained in a given bounding box. The first universal lower bound on the volume of...
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...
Geometric Thickness in a Grid (2003)
Th geometric thmetric of agraph is th minimum number of layerssuch thh th graph can be drawn in th planewith edges asstraigh-VV=V segments, andwith each edge assigned to a layer soth9 no two edges in...
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),...
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...
Bounded Degree Book Embeddings and Three-Dimensional Orthogonal Graph Drawing (2002)
A book embedding of a graph consists of a linear ordering of the vertices along a line in 3-space (the spine), and an assignment of edges to half-planes with the spine as boundary (the pages), so...
Orthogonal Drawings with Few Layers (2002)
Biedl, Therese, Johansen, John, Shermer, Thomas, Wood, David R.
In this paper, we study 3-dimensional orthogonal graph drawings. Motivated by the fact that only a limited number of layers is possible in VLSI technology, and also noting that a small number of...
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),...
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...
Bounded Degree Book Embeddings and Three-Dimensional Orthogonal Graph Drawing (2002)
A book embedding of a graph consists of a linear ordering of the vertices along a line in 3-space (the spine), and an assignment of edges to half-planes with the spine as boundary (the pages), so...
Orthogonal Drawings with Few Layers (2002)
Biedl, Therese, Johansen, John, Shermer, Thomas, Wood, David R.
In this paper, we study 3-dimensional orthogonal graph drawings. Motivated by the fact that only a limited number of layers is possible in VLSI technology, and also noting that a small number of...
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),...
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...
Bounded Degree Book Embeddings and Three-Dimensional Orthogonal Graph Drawing (2002)
A book embedding of a graph consists of a linear ordering of the vertices along a line in 3-space (the spine), and an assignment of edges to half-planes with the spine as boundary (the pages), so...
Orthogonal Drawings with Few Layers (2002)
Biedl, Therese, Johansen, John, Shermer, Thomas, Wood, David R.
In this paper, we study 3-dimensional orthogonal graph drawings. Motivated by the fact that only a limited number of layers is possible in VLSI technology, and also noting that a small number of...
Degree constrained book embeddings (2002)
A book embedding of a graph consists of a linear ordering of the vertices along a line in 3-space (the spine), and an assignment of edges to half-planes with the spine as boundary (the pages), so...
Queue layouts, tree-width, and three-dimensional graph drawing (2002)
Abstract. A three-dimensional (straight-line grid) drawing of a graph represents the vertices by points in Z 3 and the edges by non-crossing line segments. This research is motivated by the following...
Orthogonal drawings with few layers (2002)
Therese Biedl, John R. Johansen, Thomas Shermer, David R. Wood
Abstract. In this paper, we study 3-dimensional orthogonal graph drawings. Motivated by the fact that only a limited number of layers is possible in VLSI technology, and also noting that a small...
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...
Dimension-Exchange Algorithms for Load Balancing on Trees (2002)
Michael E. Houle, Antonios Symvonis, David R. Wood
This paper considers dimension-exchange algorithms for load balancing on trees with finitely-divisible loads (token distribution). We present improved analysis of an existing protocol, and in...
On vertex-magic and edge-magic total injections of graphs (2002)
The study of graph labellings has focused on nding classes of graphs which admit a particular type of labelling. Here we consider variations of the wellknown edge-magic and vertex-magic total...
Queue layouts, tree-width, and three-dimensional graph drawing (2002)
A three-dimensional (straight-line grid) drawing of a graph represents the vertices by points in Z 3 and the edges by non-crossing line segments. This research is motivated by the following open...
Queue layouts, tree-width, and three-dimensional graph drawing (2002)
Abstract. A three-dimensional (straight-line grid) drawing of a graph represents the vertices by points in Z 3 and the edges by non-crossing line segments. This research is motivated by the following...
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...
Dimension-Exchange Algorithms for Load Balancing on Trees (2002)
Michael E. Houle, Antonios Symvonis, David R. Wood
This paper considers dimension-exchange algorithms for load balancing on trees with finitely-divisible loads (token distribution). We present improved analysis of an existing protocol, and in...
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...
Dimension-Exchange Algorithms for Load Balancing on Trees (2002)
Michael E. Houle, Antonios Symvonis, David R. Wood
This paper considers dimension-exchange algorithms for load balancing on trees with finitely-divisible loads (token distribution). We present improved analysis of an existing protocol, and in...
Lower Bounds for One-to-one Packet Routing on Trees using Hot-Potato Algorithms (2002)
Roberts, Alan, Symvonis, Antonios, Wood, David R.
In this paper, we consider hot-potato packet routing of one-to-one routing patterns on $n$-node trees. By applying a ‘charging argument’, we show that any greedy hot-potato algorithm routes a...
Lower Bounds for the Number of Bends in Three-Dimensional Orthogonal Graph Drawings (2001)
In this paper we present the first non-trivial lower bounds for the total number of bends in 3-D orthogonal drawings of maximum degree six graphs. In particular, we prove lower bounds for the number...
Three-Dimensional Orthogonal Graph Drawing with Optimal Volume (2001)
Biedl, Therese, Thiele, Torsten, Wood, David R.
In this paper, we study three-dimensional orthogonal box-drawings of graphs without loops. We provide lower bounds for three scenarios: (1) drawings where vertices have bounded aspect ratio, (2)...
Refinement of Three-Dimensional Orthogonal Graph Drawings (2001)
Lynn, Benjamin Y. S., Symvonis, Antonios, Wood, David R.
In this paper we introduce a number of techniques for the refinement of three-dimensional orthogonal drawings of maximum degree six graphs. We have implemented several existing algorithms for...
Lower Bounds for the Number of Bends in Three-Dimensional Orthogonal Graph Drawings (2001)
In this paper we present the first non-trivial lower bounds for the total number of bends in 3-D orthogonal drawings of maximum degree six graphs. In particular, we prove lower bounds for the number...
Three-Dimensional Orthogonal Graph Drawing with Optimal Volume (2001)
Biedl, Therese, Thiele, Torsten, Wood, David R.
In this paper, we study three-dimensional orthogonal box-drawings of graphs without loops. We provide lower bounds for three scenarios: (1) drawings where vertices have bounded aspect ratio, (2)...
Refinement of Three-Dimensional Orthogonal Graph Drawings (2001)
Lynn, Benjamin Y. S., Symvonis, Antonios, Wood, David R.
In this paper we introduce a number of techniques for the refinement of three-dimensional orthogonal drawings of maximum degree six graphs. We have implemented several existing algorithms for...
Lower Bounds for the Number of Bends in Three-Dimensional Orthogonal Graph Drawings (2001)
In this paper we present the first non-trivial lower bounds for the total number of bends in 3-D orthogonal drawings of maximum degree six graphs. In particular, we prove lower bounds for the number...
Three-Dimensional Orthogonal Graph Drawing with Optimal Volume (2001)
Biedl, Therese, Thiele, Torsten, Wood, David R.
In this paper, we study three-dimensional orthogonal box-drawings of graphs without loops. We provide lower bounds for three scenarios: (1) drawings where vertices have bounded aspect ratio, (2)...
Refinement of Three-Dimensional Orthogonal Graph Drawings (2001)
Lynn, Benjamin Y. S., Symvonis, Antonios, Wood, David R.
In this paper we introduce a number of techniques for the refinement of three-dimensional orthogonal drawings of maximum degree six graphs. We have implemented several existing algorithms for...
Bounded degree book embeddings and three-dimensional orthogonal graph drawing (2001)
Abstract. A book embedding of a graph consists of a linear ordering of the vertices along a line in 3-space (the spine), and an assignment of edges to half-planes with the spine as boundary (the...
Balanced vertex-orderings of graphs (2001)
Therese Biedl, Timothy Chan, Yashar Ganjali, Mohammadtaghi Hajiaghayi, David R. Wood
In this paper we consider the problem of determining a balanced ordering of the vertices of a graph; that is, the neighbours of each vertex v are as evenly distributed to the left and right of v as...
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....
An algorithm for three-dimensional orthogonal graph drawing (2000)
\Design, which by another name is called drawing: :: is the fount and body of painting and sculpture and architecture: : : and the root of all sciences."
An algorithm for three-dimensional orthogonal graph drawing (2000)
This paper presents the rst non-trivial lower bounds for the total number of bends in 3-D orthogonal graph drawings with vertices represented by points. In particular, we prove lower bounds for the...
An algorithm for three-dimensional orthogonal graph drawing (2000)
This paper presents the first non-trivial lower bounds for the total number of bends in 3-D orthogonal graph drawings with vertices represented by points. In particular, we prove lower bounds for the...
An algorithm for three-dimensional orthogonal graph drawing (2000)
In this paper we present an algorithm for drawing a graph G = (V; E) with \Delta(G) 5 in the minimum-dimensional orthogonal grid. Our drawings are bounded by the hypercube of side length O(jV j) with...
An algorithm for three-dimensional orthogonal graph drawing (2000)
A 3-dimensional orthogonal drawing of graph with maximum degree at most six positions the vertices at grid-points in the 3-dimensional orthogonal grid, and routes edges along grid lines such that...
Lower Bounds for the Number of Bends in Three-Dimensional Orthogonal Graph Drawings (2000)
In this paper we present the first non-trivial lower bounds for the total number of bends in 3-D orthogonal drawings of maximum degree six graphs. In particular, we prove lower bounds for the number...
Lower Bounds for One-to-one Packet Routing on Trees using Hot-Potato Algorithms (2000)
Alan Roberts, Antonios Symvonis, David R. Wood
In this paper we consider hot-potato packet routing of one-to-one routing patterns on trees. For all sufficiently large n we construct a one-to-one packet routing problem on an n-node tree for which...
Three-Dimensional Orthogonal Graph Drawing (2000)
vii Declaration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi List of Figures ....
Three-Dimensional Orthogonal Graph Drawing (2000)
The visualisation of relational information has many applications in diverse domains such as software...
Multi-dimensional Orthogonal Graph Drawing with Small Boxes(Extended Abstract) (1999)
In this paper we investigate the general position model for the drawing of arbitrary degree graphs in the D-dimensional (D \ge 2) orthogonal grid. In this model no two vertices lie in the same grid...
Multi-dimensional Orthogonal Graph Drawing with Small Boxes(Extended Abstract) (1999)
In this paper we investigate the general position model for the drawing of arbitrary degree graphs in the D-dimensional (D \ge 2) orthogonal grid. In this model no two vertices lie in the same grid...
Multi-dimensional Orthogonal Graph Drawing with Small Boxes(Extended Abstract) (1999)
In this paper we investigate the general position model for the drawing of arbitrary degree graphs in the D-dimensional (D \ge 2) orthogonal grid. In this model no two vertices lie in the same grid...
Multi-dimensional orthogonal graph drawing with small boxes (1999)
davidwcsse. monash. edu. au Abstract. In this paper we investigate the general position model for the drawing of arbitrary degree graphs in the D-dimensional (D _> 2) orthogonal grid. In this...
A New Algorithm and Open Problems in Three-Dimensional Orthogonal Graph Drawing (1999)
. In this paper we present an algorithm for 3-D orthogonal drawing of arbitrary degree n-vertex m-edge multigraphs with O(m 2 = p n) bounding box volume and 6 bends per edge route. This is the...
Multi-Dimensional Orthogonal Graph Drawing in the General Position Model (1999)
In this paper we investigate the general position model for the drawing of arbitrary degree graphs in the D-dimensional (D 2) orthogonal grid. In this model no two vertices lie in the same grid...
An Algorithm for Three-Dimensional Orthogonal Graph Drawing (1998)
In this paper we present an algorithm for 3-dimensional orthogonal graph drawing based on the movement of vertices from an initial layout along the main diagonal of a cube. For an n-vertex m-edge...
An Algorithm for Three-Dimensional Orthogonal Graph Drawing (1998)
In this paper we present an algorithm for 3-dimensional orthogonal graph drawing based on the movement of vertices from an initial layout along the main diagonal of a cube. For an n-vertex m-edge...
An Algorithm for Three-Dimensional Orthogonal Graph Drawing (1998)
In this paper we present an algorithm for 3-dimensional orthogonal graph drawing based on the movement of vertices from an initial layout along the main diagonal of a cube. For an n-vertex m-edge...
An Algorithm for Three-Dimensional Orthogonal Graph Drawing (1998)
. In this paper we present an algorithm for 3-dimensional orthogonal graph drawing based on the movement of vertices from an initial layout along the main diagonal of a cube. For an n-vertex m-edge...
Two-Bend Three-Dimensional Orthogonal Grid Drawing of Maximum Degree Five Graphs (1998)
Some recent algorithms for 3-dimensional orthogonal graph drawing use no more than 3 bends per edge route. It is unknown if there exists a graph requiring a 3-bend edge route. In this paper we...
An algorithm for finding a maximum clique in a graph (1997)
This paper introduces a branch and bound algorithm for the maximumclique problem which applies existing clique finding and vertex coloring heuristics to determine lower and upper bounds for the size...
Towards a 2-Bends Algorithm for Three-Dimensional Orthogonal Graph Drawing (1997)
Two recent algorithms for 3-dimensional orthogonal graph drawing both guarantee no more than 3 bends per edge, yet no graph has been shown to necessarily require a 3-bend edge. In this paper we...
BGF :--a framework for board game applets /--by David R. Wood. (1996)
Submitted in partial fulfillment of the requirements for the degree, Master of Science, Computer Science.
An algorithm for #nding a maximum clique in a graph (1996)
This paper introduces a branch-and-bound algorithm for the maximum clique problem which applies existing clique #nding and vertex coloring heuristics to determine lower and upper bounds for the size...
University Microfilms order no. 9501621.
Thesis (Ph.D.)--Brigham Young University. Dept. of Family Sciences/Family Studies Program.
Behavioural science in general practice
Dr Peter Sowerby has written an important criticism of Michael Balint's work based on his understanding of Karl Popper's writings. I dispute Sowerby's interpretation of Popper and disagree with his...
Bounded-degree graphs have arbitrarily large geometric thickness
David R. Wood, Departament Matemàtica, Aplicada Ii
It is proved that there exist graphs of bounded degree with arbitrarily large queue-number. In particular, for all ∆ ≥ 3 and for all sufficiently large n, there is a simple ∆-regular n-vertex...
CLIQUE MINORS IN CARTESIAN PRODUCTS OF GRAPHS
ABSTRACT. A clique minor in a graph G can be thought of as a set of connected subgraphs in G that are pairwise disjoint and pairwise adjacent. The Hadwiger number ηÔGÕis the maximum cardinality of...