Efficient Algorithms for Petersen's Matching Theorem (2008)
Therese C. Biedl, Prosenjit Bose, Erik D. Demaine, Anna Lubiw
Petersen's theorem is a classic result in matching theory from 1891, stating that every 3-regular bridgeless graph has a perfect matching. Our work explores efficient algorithms for finding...
Therese C. Biedl, Eowyn Cenek, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, ...
. While discrepancy theory is normally only studied in the context of 2-colorings, we explore the problem of k-coloring, for k 2, a set of vertices to minimize imbalance among a family of subsets of...
Therese C. Biedl, Erik D. Demaine, Anna Lubiw
Petersen's theorem is a classic result in matching theory from 1891, stating that every 3-regular bridgeless graph has a perfect matching. Our work explores efficient algorithms for finding...
Therese C. Biedl, Erik D. Demaine, Anna Lubiw
Petersen's theorem is a classic result in matching theory from 1891, stating that every 3-regular bridgeless graph has a perfect matching. Our work explores efficient algorithms for finding...
Therese C. Biedl, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, Ming-wei Wang
b;1
Therese C. Biedl, Erik D. Demaine, Sylvain Lazard, Steven M. Robbins, Michael A. Soss
Abstract. This paper considers reconfigurations of polygons, where each polygon edge is a rigid link, no two of which can cross during the motion. We prove that one can reconfigure any monotone...
In this paper, we study three-dimensional orthogonal drawings which have at most one bend per edge. We prove a number of lower bounds and impossibilityresults for such drawings, settling open...
The complexity of Clickomania (2002)
Therese C. Biedl, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, Lars Jacobsen, J. Ian Munro
Abstract. We study a popular puzzle game known variously as Clickomania and Same Game. Basically, a rectangular grid of blocks is initially colored with some number of colors, and the player...
The complexity of Clickomania (2002)
Therese C. Biedl, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, Lars Jacobsen, J. Ian Munro
We study a popular puzzle game known variously as Clickomania and Same Game. Basically, a rectangular grid of blocks is initially colored with some number of colors, and the player repeatedly removes...
The Complexity of Clickomania (2001)
Biedl, Therese C., Demaine, Erik D., Demaine, Martin L., Fleischer, Rudolf, Jacobsen, Lars, Munro, J. Ian
We study a popular puzzle game known variously as Clickomania and Same Game. Basically, a rectangular grid of blocks is initially colored with some number of colors, and the player repeatedly removes...
Simplifying flow networks (2000)
Therese C. Biedl, Broňa Brejová
Abstract. Maximum flow problems appear in many practical applications. In this paper, we study how to simplify a given directed flow network by finding edges that can be removed without changing the...
Convexifying Monotone Polygons (1999)
Therese C. Biedl, Erik D. Demaine, Sylvain Lazard, Steven M. Robbins, Michael A. Soss
This paper considers reconfigurations of polygons, where each polygon edge is a rigid link, no two of which can cross during the motion. We prove that one can reconfigure any monotone polygon into a...
New lower bounds for orthogonal drawings (1998)
An orthogonal drawing of a graph is an embedding of the graph in the two-dimensional grid such that edges are routed along grid-lines. In this paper we explore lower bounds for orthogonal graph...
Drawing planar partitions III: Two constrained embedding problems (1998)
. In two previous papers, we studied the following problem: Given a planar graph G = (V; E) and a partition V = A [ B of the vertices. Can we draw G without crossing such that the partition is...
Drawing Planar Partitions I: LL-Drawings and LH-Drawings (1998)
Therese C. Biedl, Therese C. Biedl
. Let a planar graph G = (V; E) and a partition V = A[B of the vertices be given. Can we draw G without edge crossings such that the partition is clearly visible? Such drawings aid to display...
Hiding Disks in Folded Polygons (1998)
Therese C. Biedl, Erik D. Demaine, Martin L. Demaine, Anna Lubiw, Godfried T. Toussaint
This paper considers the problem of finding a simple fold of a given polygon P that "hides" (covers both sides of) the largest possible disk. We solve this problem by giving a...
New lower bounds for orthogonal drawings (1998)
An orthogonal drawing of a graph is an embedding of the graph in the two-dimensional grid such that edges are routed along grid-lines. In this paper we explore lower bounds for orthogonal graph...
Orthogonal graph visualization : the three-phase method with applications / (1997)
"Graduate Program in Operations Research."
Area-Efficient Static and Incremental Graph Drawings (1997)
Therese C. Biedl, Michael Kaufmann
. In this paper, we present algorithms to produce orthogonal drawings of arbitrary graphs. As opposed to most known algorithms, we do not restrict ourselves to graphs with maximum degree 4. The best...
On Triangulating Planar Graphs Under the Four-Connectivity Constraint (1997)
Therese C. Biedl, Goos Kant, And Michael Kaufmann, T. Biedl, G. Kant, 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...
The Three-Phase Method and Applications (1997)
The three-phase method is a generic method for creating orthogonal drawings of graphs of arbitrarily high degree. We provide an overview of this method and its wide range of applications. 1...
Rectangle Breaking in Grids (1997)
Paul A. Dreyer, Therese C. Biedl
Given an n \Theta n square grid, there are the outlines of n 2 1 \Theta 1 squares, (n \Gamma 1) 2 2 \Theta 2 squares, and so on. What is the minimum number of edges that can be removed from the grid...
The Three-Phase Method: A Unified Approach to Orthogonal Graph Drawing (1997)
Therese C. Biedl, Brendan P. Madden, Ioannis G. Tollis
In this paper, we study orthogonal graph drawings from a practical point of view.