Sue Whitesides

Neal Lesh, Michael Mitzenmacher, Sue Whitesides

General Terms (2008)

We present new lowest energy configurations for several large benchmark problems for the two-dimensional hydrophobichydrophilic model. We found these solutions with a generic implementation of tabu...

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

On Bus Graph Realizability ⋆ (2008)

Anil Ada, Melanie Coggan, Paul Di Marco, Alain Doyon, Liam Flookes, Ethan Kim, ...

Abstract. In this paper, we consider the following graph embedding problem: Given a bipartite graph G = (V1, V2; E), where the maximum degree of vertices in V2 is 4, can G be embedded on a two...

March 25, 2005 8:15 WSPC/Guidelines chordsep SEPARATING POINT SETS IN POLYGONAL ENVIRONMENTS (2008)

Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, ...

∗Partially supported by DURSI 2001SGR00224, Acció Integrada UPC-McGill (DURSI2004) and

Chain Reconfiguration The Ins and Outs, Ups and Downs of Moving Polygons and Polygonal Linkages (2008)

March 25, 2005 14:14 WSPC/Guidelines chordsep SEPARATING POINT SETS IN POLYGONAL ENVIRONMENTS (2008)

Abstract. A polygonal linkage or chain is a sequence of segments of fixed lengths, free to turn about their endpoints, which act as joints. This paper reviews some results in chain reconfiguration...

Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, ...

∗Partially supported by DURSI 2001SGR00224, Acció Integrada UPC-McGill (DURSI2004) and

REALIZING PARTITIONS RESPECTING FULL AND PARTIAL ORDER INFORMATION (2008)

Erik Demaine, Jeff Erickson, Danny Krizanć, Henk Meijer, Pat Morin, Mark Overmars, ...

Abstract. For n ∈ �, we consider the problem of partitioning the interval [0, n) into k subintervals of positive integer lengths ℓ1,..., ℓk such that the lengths satisfy a set of simple...

Realizing Partitions Respecting Full and Partial Order Information Abstract (2008)

Erik D. Demaine, Jeff Erickson, Henk Meijer, Pat Morin, Mark Overmars, Sue Whitesides

For n ∈ N, we consider the problem of partitioning the interval [0,n) into k subintervals of positive integer lengths ℓ1,...,ℓk such that the lengths satisfy a set of simple constraints of the...

Abstract Localizing a Robot with Minimum Travel (2008)

On the Size of the 3D Visibility Skeleton: Experimental Results (2008)

We consider the problem of localizing a robot in a known environment modeled by a simple polygon P. We assume that the robot has a map of P but is placed at an unknown location. The robot must move...

Zhang, Linqiao, Everett, Hazel, Lazard, Sylvain, Weibel, Christophe, Whitesides, Sue

The 3D visibility skeleton is a data structure used to encode global visibility information about a set of objects. Previous theoretical results have shown that for $k$ convex polytopes with $n$...

On the Size of the 3D Visibility Skeleton: Experimental Results (2008)

Zhang, Linqiao, Everett, Hazel, Lazard, Sylvain, Weibel, Christophe, Whitesides, Sue

The 3D visibility skeleton is a data structure used to encode global visibility information about a set of objects. Previous theoretical results have shown that for $k$ convex polytopes with $n$...

Parameterized Complexity of Geometric Problems (2008)

Giannopoulos, Panos, Knauer, Christian, Whitesides, Sue

This paper surveys parameterized complexity results for hard geometric algorithmic problems. It includes fixed-parameter tractable problems in graph drawing, geometric graphs, geometric covering and...

Recent Results on 3D Visibility Representation of Graphs (2007)

A visibility representation of a graph G maps vertices of G to sets in Euclidean space. An edge u; v occurs in G if and only if the objects representing u and v see each other according to some...

1 (2007)

ABSTRACT A Complete and Effective Move Set for Simplified Protein Folding (2007)

Abstract. This paper initiates the study of weak proximity drawings of graphs and demonstrates their advantages over strong proximity drawings in certain cases. Weak proximity drawings are straight...

Michael Mitzenmacher, Sue Whitesides, Neal Lesh, Neal Lesh

We present new lowest energy configurations for several large benchmark problems for the two-dimensional hydrophobic-hydrophilic model. We found these solutions with a generic implementation of tabu...

x (2007)

Hazel Everett, Anna Lubiw, Henk Meijer, Kathleen Romanik, Tom Shermer, Sue Whitesides

Visibility representations of graphs map vertices to sets in Euclidean space and express edges as visibility relations between these sets. Application areas such as VLSI wire routing and circuit...

y (2007)

Michael Godau, Sue Whitesides

This paper studies 3-dimensional visibility representations of graphs in which objects in 3-d correspond to vertices and vertical visibilities between these objects correspond to edges. We ask which...

y (2007)

Marc Van Kreveld, Jack Snoeyink, Sue Whitesides

An l-ruler is a chain of n links, each of length l. The links, which are allowed to cross, are modelled by line segments whose endpoints act as joints. A given configuration of an l-ruler is said to...

y (2007)

Therese Biedl, Erik Demaine, Martin Demaine, Sylvain Lazard, Anna Lubiw, Steve Robbins, ...

x

Localizing a Robot with Minimum Travel 3 (2007)

Lines and free line segments Tangent to Arbitrary Three-dimensional Convex Polyhedra (2007)

We consider the problem of localizing a robot in a known environment modeled by a simple polygon P. We assume that the robot has a map of P but is placed at an unknown location inside P. From its...

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

Towards an Implementation of the 3D Visibility Skeleton (2007)

Zhang, Linqiao, Everett, Hazel, Lazard, Sylvain, Whitesides, Sue

In this note we describe the contents of a video illustrating an algorithm for computing the 3D visibility skeleton of a set of disjoint convex polytopes.

Towards an Implementation of the 3D Visibility Skeleton (2007)

Zhang, Linqiao, Everett, Hazel, Lazard, Sylvain, Whitesides, Sue

In this note we describe the contents of a video illustrating an algorithm for computing the 3D visibility skeleton of a set of disjoint convex polytopes.

On Bus Graph Realizability (2006)

Ada, Anil, Coggan, Melanie, Di Marco, Paul, Doyon, Alain, Flookes, Liam, Heilala, Samuli, ...

In this paper, we consider the following graph embedding problem: Given a bipartite graph G = (V1; V2;E), where the maximum degree of vertices in V2 is 4, can G be embedded on a two dimensional grid...

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

05191 Open Problem Session Report (2006)

On the Number of Maximal Free Line Segments Tangent to Arbitrary Three-dimensional Convex Polyhedra (2005)

This is a report on an informal session intended to stimulate communication and sharing of problems. Hence the attributions and citations may contain inaccuracies, and are certainly not complete.

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

On the Number of Maximal Free Line Segments Tangent to Arbitrary Three-dimensional Convex Polyhedra (2005)

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

Transversals to line segments in three-dimensional space (2005)

Brönnimann, Hervé, Everett, Hazel, Lazard, Sylvain, Sottile, Frank, Whitesides, Sue

We completely describe the structure of the connected components of transversals to a collection of $n$ line segments in $\mathbb{R}^3$. Generically, the set of transversal to four segments consist...

On the Number of Maximal Free Line Segments Tangent to Arbitrary Three-dimensional Convex Polyhedra (2005)

Brönnimann, Hervé, Devillers, Olivier, 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.

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.

Transversals to line segments in three-dimensional space (2005)

Brönnimann, Hervé, Everett, Hazel, Lazard, Sylvain, Sottile, Frank, Whitesides, Sue

We completely describe the structure of the connected components of transversals to a collection of $n$ line segments in $\mathbb{R}^3$. Generically, the set of transversal to four segments consist...

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

On the Number of Maximal Free Line Segments Tangent to Arbitrary Three-dimensional Convex Polyhedra (2005)

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

On the Number of Maximal Free Line Segments Tangent to Arbitrary Three-dimensional Convex Polyhedra (2005)

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.

Transversals to line segments in three-dimensional space (2005)

Brönnimann, Hervé, Everett, Hazel, Lazard, Sylvain, Sottile, Frank, Whitesides, Sue

We completely describe the structure of the connected components of transversals to a collection of $n$ line segments in $\mathbb{R}^3$. Generically, the set of transversal to four segments consist...

Maintaining visibility information of planar point sets with a moving viewpoint (2005)

Olivier Devillers, Hazel Everett, Samuel Hornus, Sue Whitesides, Steve Wismathk

Abstract Given a set of n points in the plane, we consider theproblem of computing the circular ordering of the points about a viewpoint q and efficiently maintaining this or-dering information as q...

Experiments with the Fixed-Parameter Approach for Two-Layer Planarization (2004)

Suderman, Matthew, Whitesides, Sue

We present computational results of an implementation based on the fixed parameter tractability (FPT) approach for biplanarizing graphs. These results show that the implementation can efficiently...

The Three Dimensional Logic Engine (2004)

Kitching, Matthew, Whitesides, Sue

We consider the following graph embedding question: given a graph G, is it possible to map its vertices to points in 3D such that G is isomorphic to the mutual nearest neighbor graph of the set P of...

Experiments with the Fixed-Parameter Approach for Two-Layer Planarization (2004)

Suderman, Matthew, Whitesides, Sue

We present computational results of an implementation based on the fixed parameter tractability (FPT) approach for biplanarizing graphs. These results show that the implementation can efficiently...

The Three Dimensional Logic Engine (2004)

Kitching, Matthew, Whitesides, Sue

We consider the following graph embedding question: given a graph G, is it possible to map its vertices to points in 3D such that G is isomorphic to the mutual nearest neighbor graph of the set P of...

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

Experiments with the Fixed-Parameter Approach for Two-Layer Planarization (2004)

Suderman, Matthew, Whitesides, Sue

We present computational results of an implementation based on the fixed parameter tractability (FPT) approach for biplanarizing graphs. These results show that the implementation can efficiently...

The Three Dimensional Logic Engine (2004)

Kitching, Matthew, Whitesides, Sue

We consider the following graph embedding question: given a graph G, is it possible to map its vertices to points in 3D such that G is isomorphic to the mutual nearest neighbor graph of the set P of...

Separating point sets in polygonal environments (2004)

Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, ...

We consider the separability of two point sets inside a polygon by means of chords or geodesic lines. Specifically, given a set of red points and a set of blue points in the interior of a polygon, we...

Randomized algorithms for minimum distance localization (2004)

Malvika Rao, Gregory Dudek, Sue Whitesides

Abstract. We address the problem of minimum distance localization in environments that may contain self-similarities. A mobile robot is placed at an unknown location inside a ¢¤£ self-similar...

Separating point sets in polygonal environments (2004)

Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, ...

We consider the separability of two point sets inside a polygon by means of chords or geodesic lines. Specifically, given a set of red points and a set of blue points in the interior of a polygon, we...

Separating point sets in polygonal environments (2004)

Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, ...

We consider the separability of two point sets inside a polygon by means of chords or geodesic lines. Specifically, given a set of red points and a set of blue points in the interior of a polygon, we...

Transversals to Line Segments in R^3 (2003)

Brönnimann, Hervé, Everett, Hazel, Lazard, Sylvain, Sottile, Frank, Whitesides, Sue

We completely describe the structure of the connected components of transversals to a collection of n line segments in R^3. We show that n3 arbitrary line segments in R^3 admit 0, 1, , n or...

The number of transversals to line segments in R^3 (2003)

Brönnimann, Hervé, Everett, Hazel, Lazard, Sylvain, Sottile, Frank, Whitesides, Sue

We completely describe the structure of the connected components of transversals to a collection of n line segments in R^3. We show that n>2 arbitrary line segments in R^3 admit 0, 1, ..., n or...

Transversals to Line Segments in R^3 (2003)

Brönnimann, Hervé, Everett, Hazel, Lazard, Sylvain, Sottile, Frank, Whitesides, Sue

We completely describe the structure of the connected components of transversals to a collection of n line segments in R^3. We show that n3 arbitrary line segments in R^3 admit 0, 1, , n or...

Transversals to Line Segments in R^3 (2003)

Brönnimann, Hervé, Everett, Hazel, Lazard, Sylvain, Sottile, Frank, Whitesides, Sue

We completely describe the structure of the connected components of transversals to a collection of n line segments in R^3. We show that n3 arbitrary line segments in R^3 admit 0, 1, , n or...

On the Complexity of the Linkage Reconfiguration Problem (2003)

Helmut Alt, Helmut Alt, Günter Rote, Christian Knauer, Christian Knauer, Sue Whitesides, ...

We consider the problem of recon guring a linkage of rigid straight segments from a given start to a given target position with a continuous nonintersecting motion. The problem is nontrivial even for...

Experiments with the fixed-parameter approach for two-layer planarization (2003)

Matthew Suderman, Sue Whitesides

Abstract. We present computational results of an implementation based on the fixed parameter tractability (FPT) approach for biplanarizing graphs. These results show that the implementation can...

Experiments with the fixed-parameter approach for two-layer planarization (2003)

Matthew Suderman, Sue Whitesides

We present computational results of an implementation based on the fixed parameter tractability (FPT) approach for biplanarizing graphs. These results show that the implementation can efficiently...

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

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

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

Orthogonal Drawings of Cycles in 3D Space (Extended Abstract) (2001)

Di Battista, Giuseppe, Liotta, Giuseppe, Lubiw, Anna, Whitesides, Sue

Let C be a directed cycle, whose edges have each been assigned a desired direction in 3D (East, West, North, South, Up, or Down) but no length. We say that C is a shape cycle. We consider the...

Orthogonal Drawings of Cycles in 3D Space (Extended Abstract) (2001)

Di Battista, Giuseppe, Liotta, Giuseppe, Lubiw, Anna, Whitesides, Sue

Let C be a directed cycle, whose edges have each been assigned a desired direction in 3D (East, West, North, South, Up, or Down) but no length. We say that C is a shape cycle. We consider the...

Orthogonal Drawings of Cycles in 3D Space (Extended Abstract) (2001)

Di Battista, Giuseppe, Liotta, Giuseppe, Lubiw, Anna, Whitesides, Sue

Let C be a directed cycle, whose edges have each been assigned a desired direction in 3D (East, West, North, South, Up, or Down) but no length. We say that C is a shape cycle. We consider the...

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

Curvature-Constrained Shortest Paths in a Convex Polygon (2000)

Agarwal, Pankaj K., Biedl, Thérèse, Lazard, Sylvain, Robbins, Steve, Suri, Subhash, Whitesides, Sue

Let $B$ be a point robot moving in the plane, whose path is constrained to have curvature at most $1$, and let $\poly$ be a convex polygon with $n$ vertices. We study the collision-free, optimal path...

Curvature-Constrained Shortest Paths in a Convex Polygon (2000)

Agarwal, Pankaj K., Biedl, Thérèse, Lazard, Sylvain, Robbins, Steve, Suri, Subhash, Whitesides, Sue

Let $B$ be a point robot moving in the plane, whose path is constrained to have curvature at most $1$, and let $\poly$ be a convex polygon with $n$ vertices. We study the collision-free, optimal path...

Curvature-Constrained Shortest Paths in a Convex Polygon (2000)

Agarwal, Pankaj K., Biedl, Thérèse, Lazard, Sylvain, Robbins, Steve, Suri, Subhash, Whitesides, Sue

Let $B$ be a point robot moving in the plane, whose path is constrained to have curvature at most $1$, and let $\poly$ be a convex polygon with $n$ vertices. We study the collision-free, optimal path...

On Reconfiguring Tree Linkages: Trees can Lock (2000)

Therese Biedl, Erik Demaine, Martin Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, ...

It is an open problem to determine whether a polygonal chain can be "straightened" in the plane if its links are not allowed to cross. In this paper we propose a related question: whether a...

On Reconfiguring Tree Linkages: Trees can Lock (1999)

Biedl, Therese, Demaine, Erik, Demaine, Martin, Lazard, Sylvain, Lubiw, Anna, O'Rourke, Joseph, ...

It has recently been shown that any simple (i.e. nonintersecting) polygonal chain in the plane can be reconfigured to lie on a straight line, and any simple polygon can be reconfigured to be convex....

The Wobbly Logic Engine: Proving Hardness of Non-rigid Geometric Graph Representation Problems (1998)

Fekete, Sándor P., Houle, Michael E., Whitesides, Sue

The logic engine technique has been used in the past to establish the NP-hardness of a number of graph representations. The original technique can only be applied in those situations in which...

Orthogonal 3-D Graph Drawing (1998)

Biedl, Therese, Shermer, Thomas, Whitesides, Sue, Wismath, Stephen

This paper studies 3-D orthogonal grid drawings for graphs of arbitrary degree, K_{n} in particular, with vertices drawn as boxes. It establishes an asymptotic lower bound for the volume of the...

Graph Multidrawing: Finding Nice Drawings Without Defining Nice (1998)

Biedl, Therese, Marks, Joe, Ryall, Kathy, Whitesides, Sue

This paper proposes a multidrawing approach to graph drawing. Current graph-drawing systems typically produce only one drawing of a graph. By contrast, the multidrawing approach calls for...

The Wobbly Logic Engine: Proving Hardness of Non-rigid Geometric Graph Representation Problems (1998)

Fekete, Sándor P., Houle, Michael E., Whitesides, Sue

The logic engine technique has been used in the past to establish the NP-hardness of a number of graph representations. The original technique can only be applied in those situations in which...

Orthogonal 3-D Graph Drawing (1998)

Biedl, Therese, Shermer, Thomas, Whitesides, Sue, Wismath, Stephen

This paper studies 3-D orthogonal grid drawings for graphs of arbitrary degree, K_{n} in particular, with vertices drawn as boxes. It establishes an asymptotic lower bound for the volume of the...

Graph Multidrawing: Finding Nice Drawings Without Defining Nice (1998)

Biedl, Therese, Marks, Joe, Ryall, Kathy, Whitesides, Sue

This paper proposes a multidrawing approach to graph drawing. Current graph-drawing systems typically produce only one drawing of a graph. By contrast, the multidrawing approach calls for...

The Wobbly Logic Engine: Proving Hardness of Non-rigid Geometric Graph Representation Problems (1998)

Fekete, Sándor P., Houle, Michael E., Whitesides, Sue

The logic engine technique has been used in the past to establish the NP-hardness of a number of graph representations. The original technique can only be applied in those situations in which...

Orthogonal 3-D Graph Drawing (1998)

Biedl, Therese, Shermer, Thomas, Whitesides, Sue, Wismath, Stephen

This paper studies 3-D orthogonal grid drawings for graphs of arbitrary degree, K_{n} in particular, with vertices drawn as boxes. It establishes an asymptotic lower bound for the volume of the...

Graph Multidrawing: Finding Nice Drawings Without Defining Nice (1998)

Biedl, Therese, Marks, Joe, Ryall, Kathy, Whitesides, Sue

This paper proposes a multidrawing approach to graph drawing. Current graph-drawing systems typically produce only one drawing of a graph. By contrast, the multidrawing approach calls for...

On a visibility representation for graphs in three dimensions (1998)

Prosenjit Bose, Hazel Everett, Anna Lubiw, Henk Meijer, Kathleen Romanik, Thomas C. Shermer, ...

This paper proposes a 3-dimensional visibility representation of graphs G = (V; E) in which vertices are mapped to rectangles oating in R

On a visibility representation for graphs in three dimensions (1998)

Prosenjit Bose, Hazel Everett, Anna Lubiw, Henk Meijer, Kathleen Romanik, Thomas C. Shermer, ...

This paper proposes a 3-dimensional visibility representation of graphs G = (V; E) in which vertices are mapped to rectangles oating in R

On a visibility representation for graphs in three dimensions (1998)

Prosenjit Bose, Hazel Everett, Anna Lubiw, Henk Meijer, Kathleen Romanik, Thomas C. Shermer, ...

This paper proposes a 3-dimensional visibility representation of graphs G = (V; E) in which vertices are mapped to rectangles oating in R

On a visibility representation for graphs in three dimensions (1998)

Prosenjit Bose, Sdndor P. Fckete, Anna Lubiw, Thomas C. Shetruer, Michael E. Houle, Henk Meijer, ...

This paper proposes a 3-dimensional visibility representation of graphs G (V, E) in which vertices are mapped to rectangles floating in [R 3 parallel to the x, y-plane, with edges represented by...

On a visibility representation for graphs in three dimensions (1998)

Prosenjit Bose, Hazel Everett, Anna Lubiw, Henk Meijer, Kathleen Romanik, Thomas C. Shermer, ...

This paper proposes a 3-dimensional visibility representation of graphs G = (V; E) in which vertices are mapped to rectangles oating in R

Curvature-Constrained Shortest Paths in a Convex Polygon (Extended Abstract) (1998)

Pankaj K. Argarwal, Therese Biedl, Sylvain Lazard, Steve Robbins, Subhash Suri, Sue Whitesides

) Pankaj K. Agarwal Therese Biedl y Sylvain Lazard z Steve Robbins x Subhash Suri -- Sue Whitesides k Abstract Let B be a point robot moving in the plane, whose path is constrained to have curvature...

Unfolding Some Classes of Orthogonal Polyhedra (1998)

Therese Biedl, Erik Demaine, Martin Demaine, Anna Lubiw, Mark Overmars, Joseph O'Rourke, ...

In this paper, we study unfoldings of orthogonal polyhedra. More precisely, we define two special classes of orthogonal polyhedra, orthostacks and orthotubes, and show how to generate unfoldings by...

On a visibility representation for graphs in three dimensions (1998)

Prosenjit Bose, Hazel Everett, Sándor P. Fekete, Michael E. Houle, Anna Lubiw, Henk Meijer, ...

This paper proposes a 3-dimensional visibility representation of graphs G = (V,E) in which vertices are mapped to rectangles floating in R 3 parallel to the x, y-plane, with edges represented by...

On a visibility representation for graphs in three dimensions (1998)

Prosenjit Bose, Hazel Everett, Sándor P. Fekete, Michael E. Houle, Anna Lubiw, Henk Meijer, ...

This paper proposes a 3-dimensional visibility representation of graphs G = (V,E) in which vertices are mapped to rectangles floating in R 3 parallel to the x, y-plane, with edges represented by...

Two Algorithms for Three Dimensional Orthogonal Graph Drawing (1997)

Eades, Peter, Symvonis, Antonios, Whitesides, Sue

We use basic results from graph theory to design two algorithms for constructing 3-dimesional, intersection-free orthogonal grid drawings of n vertex graphs of maximum degree 6. Our first algorithm...

Two Algorithms for Three Dimensional Orthogonal Graph Drawing (1997)

Eades, Peter, Symvonis, Antonios, Whitesides, Sue

We use basic results from graph theory to design two algorithms for constructing 3-dimesional, intersection-free orthogonal grid drawings of n vertex graphs of maximum degree 6. Our first algorithm...

Two Algorithms for Three Dimensional Orthogonal Graph Drawing (1997)

Eades, Peter, Symvonis, Antonios, Whitesides, Sue

We use basic results from graph theory to design two algorithms for constructing 3-dimesional, intersection-free orthogonal grid drawings of n vertex graphs of maximum degree 6. Our first algorithm...

Angewandte Mathematik und Informatik Universit at zu K oln (1997)

Report No On, Hazel Everett, Hazel Everett, S'andor P. Fekete, S'andor P. Fekete, Michael E. Houle, ...

This paper proposes a 3-dimensional visibility representation of graphs G = (V; E) in which vertices are mapped to rectangles floating in R 3 parallel to the x; y-plane, with edges represented by...

The Wobbly Logic Engine: Proving Hardness of Non-rigid Geometric Graph Representation Problems (1997)

Sándor P. Fekete, S'andor P. Fekete, Michael E. Houle, Michael E. Houle, Michael E. Houle, Sue Whitesides, ...

In this paper we describe a general technique for establishing NPhardness of graph representations. This technique is a generalization of the tool called the logic engine. We show that it is possible...

On a Visibility Representation of Graphs in 3D (1997)

Prosenjit Bose, Hazel Everett, Hazel Everett, Sandor P. Fekete, S'andor P. Fekete, Michael E. Houle, ...

This paper proposes a 3-dimensional visibility representation of graphs G = (V; E) in which vertices are mapped to rectangles floating in R 3 parallel to the x; y-plane, with edges represented by...

Two Algorithms for Three Dimensional Orthogonal Graph Drawing (1997)

Peter Eades, Antonios Symvonis, Sue Whitesides

We use basic results from graph theory to design two algorithms for constructing 3-dimensional, intersection-free orthogonal grid drawings of n vertex graphs of maximum degree 6. Our first algorithm...

Two Algorithms for Three Dimensional Orthogonal Graph Drawing (1997)

Peter Eades, Antonios Symvonis, Sue Whitesides

uter Science, University of Sydney, N.S.W. 2006, Australia, supported by an ARC Institutional grant, symvonis@cs.su.oz.au z School of Computer Science, McGill University, Montreal, Canada H3A 2A7,...

The Strength of Weak Proximity (Extended Abstract) (1996)

Di Battista, Giuseppe, Liotta, Giuseppe, Whitesides, Sue

This paper initiates the study of weak proximity drawings of graphs and demonstrates their advantages over strong proximity drawings in certain cases. Weak proximity drawings are straight line...

New Results on a Visibility Representation of Graphs in 3D (1996)

Fekete, Sándor P., Houle, Michael E., Whitesides, Sue

This paper considers a 3-dimensional visibility representation of cliques K_n. In this representation, the objects representing the vertices are 2-dimensional and lie parallel to the x, y-plane, and...

Universal 3-Dimensional Visibility Representations Graphs (1996)

The Strength of Weak Proximity (Extended Abstract) (1996)

This paper studies 3-dimensional visibility representations of graphs in which objects in 3-d correspond to vertices and vertical visibilities between these objects correspond to edges. We ask which...

Di Battista, Giuseppe, Liotta, Giuseppe, Whitesides, Sue

This paper initiates the study of weak proximity drawings of graphs and demonstrates their advantages over strong proximity drawings in certain cases. Weak proximity drawings are straight line...

New Results on a Visibility Representation of Graphs in 3D (1996)

Fekete, Sándor P., Houle, Michael E., Whitesides, Sue

This paper considers a 3-dimensional visibility representation of cliques K_n. In this representation, the objects representing the vertices are 2-dimensional and lie parallel to the x, y-plane, and...

Universal 3-Dimensional Visibility Representations Graphs (1996)

The Strength of Weak Proximity (Extended Abstract) (1996)

This paper studies 3-dimensional visibility representations of graphs in which objects in 3-d correspond to vertices and vertical visibilities between these objects correspond to edges. We ask which...

Di Battista, Giuseppe, Liotta, Giuseppe, Whitesides, Sue

This paper initiates the study of weak proximity drawings of graphs and demonstrates their advantages over strong proximity drawings in certain cases. Weak proximity drawings are straight line...

New Results on a Visibility Representation of Graphs in 3D (1996)

Fekete, Sándor P., Houle, Michael E., Whitesides, Sue

This paper considers a 3-dimensional visibility representation of cliques K_n. In this representation, the objects representing the vertices are 2-dimensional and lie parallel to the x, y-plane, and...

Universal 3-Dimensional Visibility Representations Graphs (1996)

Simultaneous Dominance Representation of Multiple Posets (1996)

This paper studies 3-dimensional visibility representations of graphs in which objects in 3-d correspond to vertices and vertical visibilities between these objects correspond to edges. We ask which...

Paul J. Tanenbaum, Paul J. Tanenbaum, Sue Whitesides, Sue Whitesides, Projet Prisme

: We characterize the codominance pairspairs of posets that admit simultaneous dominance representations in the (x; y)- and (\Gammax; y)-coordinate systemsand present a linear algorithm to recognize...

Strategic Directions in Computational Geometry (1996)

Roberto Tamassia, Roberto Tamassia (editor, Pankaj K. Agarwal, Nancy Amato, Danny Z. Chen, David Dobkin, ...

ing with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works, requires prior specific permission...

New Results on a Visibility Representation of Graphs in 3D (1996)

Sandor P. Fekete, S'andor P. Fekete, S'andor P. Fekete, Michael E. Houle, Michael E. Houle, Michael E. Houle, ...

This paper considers a 3-dimensional visibility representation of cliques K n . In this representation, the objects representing the vertices are 2dimensional and lie parallel to the x; y-plane, and...

New Results on a Visibility Representation of Graphs in 3D (1996)

Sandor P. Fekete, S'andor P. Fekete, S'andor P. Fekete, Michael E. Houle, Michael E. Houle, Michael E. Houle, ...

This paper considers a 3-dimensional visibility representation of cliques K n . In this representation, the objects representing the vertices are 2dimensional and lie parallel to the x; y-plane, and...

Simultaneous Dominance Representation of Multiple Posets (1996)

Paul J. Tanenbaum, Sue Whitesides

We characterize the codominance pairs---pairs of posets that admit simultaneous dominance representations in the (x; y)- and (\Gammax; y)-coordinate systems---and present a linear algorithm to...

Folding Rulers inside Triangles (1996)

Marc Van Kreveld, Jack Snoeyink, Sue Whitesides

An l-ruler is a chain of n links, each of length l. The links, which are allowed to cross, are modelled by line segments whose endpoints act as joints. A given configuration of an l-ruler is said to...

Universal 3-Dimensional Visibility Representations for Graphs (1995)

Simultaneous Dominance Representation of Multiple Posets (1995)

This paper studies 3-dimensional visibility representations of graphs in which objects in 3-d correspond to vertices and vertical visibilities between these objects correspond to edges. We ask which...

Tanenbaum, J., Whitesides, Sue

We characterize he {\em codominance pairs} pairs of posets that admit simultaneous dominance representations in the $(x,y)$- and $(-x,y)$-coordinate systems and present a linear algorithm to...

Recognizing Rectangle of Influence Drawable Graphs (extended abstract) (1995)

ElGindy, H., Liotta, Giuseppe, Lubiw, Anna, Meijer, Henk, Whitesides, Sue

Given two points x and y in the plane the rectangle of influence of x and y is the axis-aligned rectangle having x and y at opposite corners. The rectangle of influence drawing of a graph G is a...

Poster Gallery Report (1995)

Recognizing Rectangle of Influence Drawable Graphs (extended abstract) (1995)

We describe different methods for three dimensional embedding of graphs, as well as a two dimensional layout method, namely barycentric embedding. In addition, we present a program for automatic...

ElGindy, H., Liotta, Giuseppe, Lubiw, Anna, Meijer, Henk, Whitesides, Sue

Given two points x and y in the plane the rectangle of influence of x and y is the axis-aligned rectangle having x and y at opposite corners. The rectangle of influence drawing of a graph G is a...

Poster Gallery Report (1995)

Universal 3-Dimensional Visibility Representations for Graphs (1995)

We describe different methods for three dimensional embedding of graphs, as well as a two dimensional layout method, namely barycentric embedding. In addition, we present a program for automatic...

Simultaneous Dominance Representation of Multiple Posets (1995)

This paper studies 3-dimensional visibility representations of graphs in which objects in 3-d correspond to vertices and vertical visibilities between these objects correspond to edges. We ask which...

Tanenbaum, J., Whitesides, Sue

We characterize he {\em codominance pairs} pairs of posets that admit simultaneous dominance representations in the $(x,y)$- and $(-x,y)$-coordinate systems and present a linear algorithm to...

Universal 3-Dimensional Visibility Representations for Graphs (1995)

Simultaneous Dominance Representation of Multiple Posets (1995)

This paper studies 3-dimensional visibility representations of graphs in which objects in 3-d correspond to vertices and vertical visibilities between these objects correspond to edges. We ask which...

Tanenbaum, J., Whitesides, Sue

We characterize he {\em codominance pairs} pairs of posets that admit simultaneous dominance representations in the $(x,y)$- and $(-x,y)$-coordinate systems and present a linear algorithm to...

Recognizing Rectangle of Influence Drawable Graphs (extended abstract) (1995)

ElGindy, H., Liotta, Giuseppe, Lubiw, Anna, Meijer, Henk, Whitesides, Sue

Given two points x and y in the plane the rectangle of influence of x and y is the axis-aligned rectangle having x and y at opposite corners. The rectangle of influence drawing of a graph G is a...

Poster Gallery Report (1995)

Universal 3-Dimensional Visibility Representations for Graphs (1995)

We describe different methods for three dimensional embedding of graphs, as well as a two dimensional layout method, namely barycentric embedding. In addition, we present a program for automatic...

Helmut Alt, Helmut Alt, Michael Godau, Michael Godau, Sue Whitesides, Sue Whitesides, ...

This paper studies 3-dimensional visibility representations of graphs in which objects in 3-d correspond to vertices and vertical visibilities between these objects correspond to edges. We ask which...

Angewandte Mathematik und Informatik Universit at zu K oln (1995)

Report No On, Qu'ebec Ga H, Hazel Everett, Hazel Everett, S'andor P. Fekete, S'andor P. Fekete, ...

Visibility representations of graphs map vertices to sets in Euclidean space and express edges as visibility relations between these sets. Application areas such as VLSI wire routing and circuit...

Localizing a Robot with Minimum Travel (1995)

The Techniques of Komolgorov and Bardzin for Three Dimensional Orthogonal Graph Drawings (1995)

We consider the problem of localizing a robot in a known environment modeled by a simple polygon P . We assume that the robot has a map of P but is placed at an unknown location. The robot must move...

Peter Eades, Charles Stirk, Sue Whitesides

This paper appears as Technical Report 95-07, Department of Computer Science, University of Newcastle, Newcastle NSW 2308 Australia.

Localizing a Robot with Minimum Travel (1995)