Biedl, Therese, Durocher, Stephane, Hoos, Holger H., Luan, Shuang, Saia, Jared, Young, Maxwell
he segment minimization problem consists of finding the smallest set of integer matrices that sum to a given intensity matrix, such that each summand has only one non-zero value, and the non-zeroes...
What is the best worst-case guarantee one can make on the number of bends required to embed a graph into a particular grid, in particular, the hexagonal and octagonal grids? A grid pointdrawing of a...
Efficient View Point Selection for Silhouettes of Convex Polyhedra (2008)
Abstract. The silhouette of polyhedra is an important primitive in application areas such as machine vision and computer graphics. In this paper, we study how to select view points of convex...
What is the best worst-case guarantee one can make on the number of bends required to embed a graph into a particular grid, in particular, the hexagonal and octagonal grids? A grid pointdrawing of a...
Ziv Bar-joseph, Therese Biedl, Broňa Brejová, Erik D. Demaine, David K. Gifford, Angèle M. Hamel, ...
Abstract. In this paper, we study how to present gene expression data to display similarities by trying to find a linear ordering of genes such that genes with similar expression profiles will be...
Cauchy’s Theorem and Edge Lengths of Convex (2008)
Therese Biedl, Anna Lubiw, Michael Spriggs
Abstract. In this paper we explore, from an algorithmic point of view, the extent to which the facial angles and combinatorial structure of a convex polyhedron determine the polyhedron—in...
Abstract Parallel Morphing of Trees and Cycles ∗ (2008)
Therese Biedl, Anna Lubiw, Michael J. Spriggs
We prove that for any two simple chains [more generally, trees] in R d with corresponding edges parallel, there is a parallel morph between them—i.e. a morph in which all intermediate chains...
Cauchy’s Theorem and Edge Lengths of Convex (2008)
Therese Biedl, Anna Lubiw, Michael Spriggs
Abstract. In this paper we explore, from an algorithmic point of view, the extent to which the facial angles and combinatorial structure of a convex polyhedron determine the polyhedron—in...
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...
Optimal Dynamic Video-On-Demand using Adaptive Broadcasting (2008)
Therese Biedl, Erik D. Demaine, Er Golynski, Joseph D. Horton, Ro López-ortiz, Guillaume Poirier, ...
Abstract. We consider the transmission of a movie over a broadcast network to support several viewers who start watching at arbitrary times, after a wait of at most twait minutes. A recent approach...
Therese Biedl, Erik Demaine, Martin Demaine, Sylvain Lazard, Anna Lubiw, Steve Robbins, ...
Whitesides d a
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...
Therese Biedl, Jonathan F. Buss, Erik D. Demaine, Martin L. Demaine, Mohammadtaghi Hajiaghayi
y, Tomas Vinar
Therese Biedl, Jonathan F. Buss, Erik D. Demaine, Martin L. Demaine, Mohammadtaghi Hajiaghayi
y, Tomas Vinar
Therese Biedl, Timothy Chan, Erik D. Demaine, Rudolf Fleischer, Mordecai Golin, J. Ian Munro
In this paper we study greedy in-place sorting algorithms which miraculously happen to work in reasonable time. Dumb-Sort which repeatedly compares all possible pairs of array cells sorts n elements...
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...
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...
Therese Biedl, John R. Johansen, Thomas Shermer
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...
Drawing K 2;n : A Lower Bound (2007)
Therese Biedl, Timothy M. Chan
In graph drawing [1], the main objective is to obtain a representation of a graph in the plane under some aesthetic or functional criteria. For the purposes
Therese Biedl, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Paul Nijjar, Ryuhei Uehara, ...
We prove that there is a polyhedron with genus 6 whose faces are orthogonal polygons (equivalently, rectangles) and yet the angles between some faces are not multiples of 90, so the polyhedron itself...
Therese Biedl, Erik D. Demaine, Angele M. Hamel
We design ecient competitive algorithms for discovering information hidden by an adversary. Specically, consider a game in a given interval graph G in which the adversary chooses an independent set X...
Two Open Problems Solved (2007)
This paper studies three-dimensional orthogonal box-drawings where edge-routes have at most one bend. Two open problems for such drawings are: (1) Does every drawing of Kn have volume# n
Therese Biedl, Erik Demaine, Martin Demaine, Sylvain Lazard, Anna Lubiw, Steve Robbins, ...
Whitesides d a
Fun-Sort --- Or the Chaos of Unordered (2007)
Binary Search Therese, Therese Biedl, Timothy Chan, Erik D. Demaine, Rudolf Fleischer, Mordecai Golin, ...
Usually, binary search only makes sense in sorted arrays. We show that insertion sort based on repeated "binary searches" in an initially unsorted array also sorts n elements in time #(n...
Partitions of Graphs into Trees (2007)
Biedl, Therese, Brandenburg, Franz J.
In this paper, we study the k-tree partition problem which is a partition of the set of edges of a graph into k edge-disjoint trees. This problem occurs at several places with applications e.g. in...
Partitions of Graphs into Trees (2007)
Biedl, Therese, Brandenburg, Franz J.
In this paper, we study the k-tree partition problem which is a partition of the set of edges of a graph into k edge-disjoint trees. This problem occurs at several places with applications e.g. in...
Partitions of graphs into trees (2007)
Abstract. In this paper, we study the k-tree partition problem which is a partition of the set of edges of a graph into k edge-disjoint trees. This problem occurs at several places with applications...
Crossings and Permutations (2006)
Biedl, Therese, Brandenburg, Franz J., Deng, Xiaotie
We investigate crossing minimization problems for a set of permutations, where a crossing expresses a disarrangement between elements. The goal is a common permutation pi which minimizes the number...
Morphing Planar Graphs While Preserving Edge Directions (2006)
Biedl, Therese, Lubiw, Anna, Spriggs, Michael
Two straight-line drawings P,Q of a graph (V,E) are called parallel if, for every edge (u,v) in E, the vector from u to v has the same direction in both P and Q. We study problems of the form: given...
Crossings and Permutations (2006)
Biedl, Therese, Brandenburg, Franz J., Deng, Xiaotie
We investigate crossing minimization problems for a set of permutations, where a crossing expresses a disarrangement between elements. The goal is a common permutation pi which minimizes the number...
Morphing Planar Graphs While Preserving Edge Directions (2006)
Biedl, Therese, Lubiw, Anna, Spriggs, Michael
Two straight-line drawings P,Q of a graph (V,E) are called parallel if, for every edge (u,v) in E, the vector from u to v has the same direction in both P and Q. We study problems of the form: given...
Crossings and Permutations (2006)
Biedl, Therese, Brandenburg, Franz J., Deng, Xiaotie
We investigate crossing minimization problems for a set of permutations, where a crossing expresses a disarrangement between elements. The goal is a common permutation pi which minimizes the number...
Morphing Planar Graphs While Preserving Edge Directions (2006)
Biedl, Therese, Lubiw, Anna, Spriggs, Michael
Two straight-line drawings P,Q of a graph (V,E) are called parallel if, for every edge (u,v) in E, the vector from u to v has the same direction in both P and Q. We study problems of the form: given...
Drawing Planar Bipartite Graphs With Small Area (2005)
Biedl, Therese, Brandenburg, Franz J.
In this paper, we study planar straight-line drawings of bipartite planar graphs. We show that these graphs admit drawings in an n/2 x (n/2-1) -grid, and that this is optimal. Our results generalize...
Drawing Planar Bipartite Graphs With Small Area (2005)
Biedl, Therese, Brandenburg, Franz J.
In this paper, we study planar straight-line drawings of bipartite planar graphs. We show that these graphs admit drawings in an n/2 x (n/2-1) -grid, and that this is optimal. Our results generalize...
Drawing Planar Bipartite Graphs With Small Area (2005)
Biedl, Therese, Brandenburg, Franz J.
In this paper, we study planar straight-line drawings of bipartite planar graphs. We show that these graphs admit drawings in an n/2 x (n/2-1) -grid, and that this is optimal. Our results generalize...
Hexagonal Grid Drawings: Algorithms and Lower Bounds (2004)
Aziza, Shabnam, Biedl, Therese
We study drawings of graphs of maximum degree six on the hexagonal (triangular) grid, with the main focus of keeping the number of bends small. We give algorithms that achieve 3.5n + 3.5 bends for...
Hexagonal Grid Drawings: Algorithms and Lower Bounds (2004)
Aziza, Shabnam, Biedl, Therese
We study drawings of graphs of maximum degree six on the hexagonal (triangular) grid, with the main focus of keeping the number of bends small. We give algorithms that achieve 3.5n + 3.5 bends for...
Hexagonal Grid Drawings: Algorithms and Lower Bounds (2004)
Aziza, Shabnam, Biedl, Therese
We study drawings of graphs of maximum degree six on the hexagonal (triangular) grid, with the main focus of keeping the number of bends small. We give algorithms that achieve 3.5n + 3.5 bends for...
Finding hidden independent sets in interval graphs. Theoretical Computer Science (2004)
Therese Biedl, Broňa Brejová, Erik D. Demaine, Angèle M. Hamel, Ro López-ortiz
We design efficient competitive algorithms for discovering hidden information using few queries. Specifically, consider a game in a given set of intervals (and their implied interval graph G) in...
Finding hidden independent sets in interval graphs. Theoretical Computer Science (2004)
Therese Biedl, Erik D. Demaine, Ang`ele M. Hamel
1 Introduction An interval graph is an intersection graph of intervals on the real line, i.e. vertices are represented by intervals and there is an edge between two vertices if and only if their...
Tight bounds on maximal and maximum matchings (2004)
Therese Biedl, Erikd. Demaine, Christian A. Duncan, Rudolf Fleischer, Stephen G. Kobourov
Abstract. In this paper, we study bounds on maximal and maximum matchings in special graph classes, specifically triangulated graphs and graphs with bounded maximum degree. For each class, we give a...
Tight bounds on maximal and maximum matchings (2004)
Therese Biedl, Erik D. Demaine, Christian A. Duncan, Rudolf Fleischer, Stephen G. Kobourov
Abstract. In this paper, we study bounds on maximal and maximum matchings in special graph classes, specifically triangulated graphs and graphs with bounded maximum degree. For each class, we give a...
Tight bounds on maximal and maximum matchings (2004)
Therese Biedl, Erik D. Demaine, Christian A. Duncan, Rudolf Fleischer, Stephen G. Kobourov
In this paper, we study lower bounds on the size of maximal and maximum matchings in 3-connected planar graphs and graphs with bounded maximum degree. For each class, we give a lower bound on the...
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...
Finding hidden independent sets in interval graphs. Theoretical Computer Science (2004)
Therese Biedl, Erik D. Demaine, Ang`ele M. Hamel
1 Introduction An interval graph is an intersection graph of intervals on the real line, i.e. vertices are represented by intervals and there is an edge between two vertices if and only if their...
Kissing Circle Representation (2003)
Stan Wagon, Fhns Stefan Felsner, Ferrán Hurtado, Ileana Streinu Hamiltonicity, Therese Biedl
Is every zonohedron 3-colorable when viewed as a planar map? This question arose out of work described in [RSW01]. An equivalent question, under a different guise, is posed in [FHNS00]: Is the...
Drawing Outer-Planar Graphs in O(n log n) Area (2002)
In this paper, we study drawings of outer-planar graphs in various models. We show that O(n log n) area can be achieved for such drawings if edges are allowed to have bends or if vertices may be...
Graph-Drawing Contest Report (2002)
Biedl, Therese, Brandenburg, Franz J.
This report describes the Eight Annual Graph Drawing Contest, held in conjunction with the Ninth Graph Drawing Symposium in Vienna, Austria. The purpose of the contest is to monitor and challenge the...
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...
Drawing Outer-Planar Graphs in O(n log n) Area (2002)
In this paper, we study drawings of outer-planar graphs in various models. We show that O(n log n) area can be achieved for such drawings if edges are allowed to have bends or if vertices may be...
Graph-Drawing Contest Report (2002)
Biedl, Therese, Brandenburg, Franz J.
This report describes the Eight Annual Graph Drawing Contest, held in conjunction with the Ninth Graph Drawing Symposium in Vienna, Austria. The purpose of the contest is to monitor and challenge the...
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...
Drawing Outer-Planar Graphs in O(n log n) Area (2002)
In this paper, we study drawings of outer-planar graphs in various models. We show that O(n log n) area can be achieved for such drawings if edges are allowed to have bends or if vertices may be...
Graph-Drawing Contest Report (2002)
Biedl, Therese, Brandenburg, Franz J.
This report describes the Eight Annual Graph Drawing Contest, held in conjunction with the Ninth Graph Drawing Symposium in Vienna, Austria. The purpose of the contest is to monitor and challenge the...
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...
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...
Tighter bounds on the genus of nonorthogonal polyhedra built from rectangles (2002)
Therese Biedl, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Paul Nijjar, Ryuhei Uehara, ...
Biedl, Therese, Chan, Timothy, Demaine, Erik D., Fleischer, Rudolf H., Golin, Mordecai J., Munro, J. Ian
In this paper we study greedy in-place sorting algorithms which miraculously happen to work in reasonable time. Dumb-Sort which repeatedly compares all possible pairs of array cells sorts n elements...
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)...
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)...
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)...
Balanced vertex-orderings of graphs (2001)
Therese Biedl, Timothy Chan, Mohammadtaghi Hajiaghayi, Yashar Ganjali
In this paper we consider the problem of determining a balanced ordering of the vertices of a graph; that is, the neighbouts of each vertex v are as evenly distributed to the left and right of v as...
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...
Therese Biedl, Broňa Brejová, Erik D. Demaine, Angèle M. Hamel
Abstract. In this paper, we study how to present gene expression data to display similarities by trying to find a linear ordering of genes such that genes with similar expression profiles will be...
1-bend 3-D orthogonal box-drawings: Two open problems solved (2001)
This paper studies three-dimensional orthogonal box-drawings where edge-routes have at most one bend. Two open problems for such drawings are: (1) Does every drawing of Kn have volume Ω(n 3)? (2)...
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....
Rectangle of Influence Drawings of Graphs without Filled 3-Cycles (1999)
Biedl, Therese, Bretscher, Anna, Meijer, Henk
In this paper, we study rectangle of influence drawings, i. e., drawings of graphs such that for any edge the axis-parallel rectangle defined by the two endpoints of the edge is empty. Specifically,...
Rectangle of Influence Drawings of Graphs without Filled 3-Cycles (1999)
Biedl, Therese, Bretscher, Anna, Meijer, Henk
In this paper, we study rectangle of influence drawings, i. e., drawings of graphs such that for any edge the axis-parallel rectangle defined by the two endpoints of the edge is empty. Specifically,...
Rectangle of Influence Drawings of Graphs without Filled 3-Cycles (1999)
Biedl, Therese, Bretscher, Anna, Meijer, Henk
In this paper, we study rectangle of influence drawings, i. e., drawings of graphs such that for any edge the axis-parallel rectangle defined by the two endpoints of the edge is empty. Specifically,...
When Can a Net Fold to a Polyhedron? (1999)
Therese Biedl, Anna Lubiw, Julie Sun
this paper, we study the problem of whether a polyhedron can be obtained from a net , i.e., a polygon and a set of creases, by folding along the creases. We consider two cases, depending on whether...
When can a net fold to a polyhedron (1999)
Therese Biedl, Anna Lubiw, Julie Sun, Communicated J. Snoeyink
www.elsevier.com/locate/comgeo In this paper, we study the problem of whether a polyhedron can be obtained from a net by folding along the creases. We show that this problem can be solved in...
The Three-Phase Method: A Unified Approach to Orthogonal Graph Drawing (1998)
Biedl, Therese, Madden, Brendan, Tollis, Ioannis G.
In this paper, we study orthogonal graph drawings from a practical point of view. Most previously existing algorithms restricted the attention to graphs of maximum degree four. Here we study...
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...
Three Approaches to 3D-Orthogonal Box-Drawings (Extended Abstract) (1998)
In this paper, we study orthogonal graph drawings in three dimensions with nodes drawn as boxes. The algorithms that we present can be differentiated as resulting from three different approaches to...
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 Three-Phase Method: A Unified Approach to Orthogonal Graph Drawing (1998)
Biedl, Therese, Madden, Brendan, Tollis, Ioannis G.
In this paper, we study orthogonal graph drawings from a practical point of view. Most previously existing algorithms restricted the attention to graphs of maximum degree four. Here we study...
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...
Three Approaches to 3D-Orthogonal Box-Drawings (Extended Abstract) (1998)
In this paper, we study orthogonal graph drawings in three dimensions with nodes drawn as boxes. The algorithms that we present can be differentiated as resulting from three different approaches to...
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 Three-Phase Method: A Unified Approach to Orthogonal Graph Drawing (1998)
Biedl, Therese, Madden, Brendan, Tollis, Ioannis G.
In this paper, we study orthogonal graph drawings from a practical point of view. Most previously existing algorithms restricted the attention to graphs of maximum degree four. Here we study...
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...
Three Approaches to 3D-Orthogonal Box-Drawings (Extended Abstract) (1998)
In this paper, we study orthogonal graph drawings in three dimensions with nodes drawn as boxes. The algorithms that we present can be differentiated as resulting from three different approaches to...
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...
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 Reconfiguring Tree Linkages: Trees can Lock (1998)
Therese Biedl, Erik Demaine, Martin Demaine, Sylvain Lazard, Anna Lubiw, Steve Robbins, ...
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. This problem been raised independently by several...
On triangulating planar graphs under the four-connectivity constraint (1997)
T. Biedl, T. Biedl, G. Kant, G. Kant, M. Kaufmann, M. Kaufmann, ...
Triangulation of planar graphs under constraints is a fundamental problem in the representation of objects. Related keywords are graph augmentation from the field of graph algorithms and mesh...
New Lower Bounds for Orthogonal Graph Drawings (1996)
An orthogonal drawing is an embedding of a graph such that edges are drawn as sequences of horizontal and vertical segments. In this paper we explore lower bounds. We find lower bounds on the number...
New Lower Bounds for Orthogonal Graph Drawings (1996)
An orthogonal drawing is an embedding of a graph such that edges are drawn as sequences of horizontal and vertical segments. In this paper we explore lower bounds. We find lower bounds on the number...
New Lower Bounds for Orthogonal Graph Drawings (1996)
An orthogonal drawing is an embedding of a graph such that edges are drawn as sequences of horizontal and vertical segments. In this paper we explore lower bounds. We find lower bounds on the number...
A Better Heuristic for Orthogonal Graph Drawings (1994)
Therese Biedl, Therese Biedl, Therese Biedl, Goos Kant, Goos Kant, Goos Kant
An orthogonal drawing of a graph is an embedding in the plane such that all edges are drawn as sequences of horizontal and vertical segments. We present a linear time and space algorithm to draw any...
Fun-Sort --- Or the Chaos of Unordered (1994)
Binary Search Therese, Therese Biedl, Timothy Chan, Erik D. Demaine, Rudolf Fleischer, Mordecai Golin, ...
Usually, binary search only makes sense in sorted arrays. We show that insertion sort based on repeated "binary searches" in an initially unsorted array also sorts n elements in time #(n...
Graph Multidrawing: Finding Nice Drawings Without Defining Nice
Therese Biedl, Joe Marks, Kathy Ryall, Sue Whitesides
. 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...