Planar Drawings of Higher-Genus Graphs (2009)
Duncan, Christian A., Goodrich, Michael T., Kobourov, Stephen G.
In this paper, we give polynomial-time algorithms that can take a graph G with a given combinatorial embedding on an orientable surface S of genus g and produce a planar drawing of G in R^2, with a...
Abstract Optimal Constrained Graph Exploration ∗ (2008)
We address the problem of constrained exploration of an unknown graph G = (V, E) from a given start node s with either a tethered robot or a robot with a fuel tank of limited capacity, the former...
Christian A. Duncan, Alon Efrat, Stephen Kobourov, Carola Wenk
Communicated by Editor’s name Traditionally, graph drawing algorithms represent vertices as circles and edges as curves connecting the vertices. We introduce the problem of drawing with “fat ”...
Graph Drawing Contest Report (2008)
Duncan, Christian A., Kobourov, Stephen G., Sander, Georg
This report describes the $14^th$ Annual Graph Drawing Contest, held in conjunction with the 2007 Graph Drawing Symposium in Sydney, Australia. The purpose of the contest is to monitor and challenge...
Graph Drawing Contest Report (2008)
Duncan, Christian A., Kobourov, Stephen G., Sander, Georg
This report describes the $14^th$ Annual Graph Drawing Contest, held in conjunction with the 2007 Graph Drawing Symposium in Sydney, Australia. The purpose of the contest is to monitor and challenge...
Christian A. Duncan, Alon Efrat, Stephen G. Kobourov, Carola Wenk
Abstract. In this paper, we introduce the problem of drawing with "fat " edges. Traditionally, graph drawing algorithms represent vertices as circles and edges as closed curves...
Christian A. Duncan, Stephen G. Kobourov
Abstract. We present a novel way to draw planar graphs with good angular resolution. We introduce the polar coordinate representation and describe a family of algorithms which use polar...
Graph-Drawing Contest Report (2007)
Duncan, Christian A., Klau, Gunnar, Kobourov, Stephen G., Sander, Georg
This report describes the Thirteenth Annual Graph Drawing Contest, held in conjunction with the 2006 Graph Drawing Symposium in Karlsruhe, Germany. The purpose of the contest is to monitor and...
Graph-Drawing Contest Report (2007)
Duncan, Christian A., Klau, Gunnar, Kobourov, Stephen G., Sander, Georg
This report describes the Thirteenth Annual Graph Drawing Contest, held in conjunction with the 2006 Graph Drawing Symposium in Karlsruhe, Germany. The purpose of the contest is to monitor and...
Graph-Drawing Contest Report (2004)
Brandenburg, Franz J., Duncan, Christian A., Gansner, Emden R., Kobourov, Stephen G.
This report describes the Eleventh Annual Graph Drawing Contest, held in conjunction with the 2004 Graph Drawing Symposium in New York, USA. The purpose of the contest is to monitor and challenge the...
Graph-Drawing Contest Report (2004)
Brandenburg, Franz J., Duncan, Christian A., Gansner, Emden R., Kobourov, Stephen G.
This report describes the Eleventh Annual Graph Drawing Contest, held in conjunction with the 2004 Graph Drawing Symposium in New York, USA. The purpose of the contest is to monitor and challenge the...
Graph-Drawing Contest Report (2004)
Brandenburg, Franz J., Duncan, Christian A., Gansner, Emden R., Kobourov, Stephen G.
This report describes the Eleventh Annual Graph Drawing Contest, held in conjunction with the 2004 Graph Drawing Symposium in New York, USA. The purpose of the contest is to monitor and challenge the...
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...
The Geometric Thickness of Low Degree Graphs (2003)
Duncan, Christian A., Eppstein, David, Kobourov, Stephen G.
We prove that the geometric thickness of graphs whose maximum degree is no more than four is two. All of our algorithms run in O(n) time, where n is the number of vertices in the graph. In our...
Christian A. Duncan, Stephen G. Kobourov, David Eppstein
We prove that the geometric thickness of graphs whose maximum degree is no more than four is two. In our proofs, we present a space and time efficient embedding technique for graphs with maximum...
Polar Coordinate Drawing of Planar Graphs with Good Angular Resolution (2002)
Duncan, Christian A., Kobourov, Stephen G.
We present a novel way to draw planar graphs with good angular resolution. We introduce the polar coordinate representation and describe a family of algorithms which use polar representation. The...
Duncan, Christian A., Efrat, Alon, Kobourov, Stephen G., Wenk, Carola
In this paper, we introduce the problem of drawing with "fat" edges. Traditionally, graph drawing algorithms represent vertices as circles and edges as closed curves connecting the vertices. In this...
Polar Coordinate Drawing of Planar Graphs with Good Angular Resolution (2002)
Duncan, Christian A., Kobourov, Stephen G.
We present a novel way to draw planar graphs with good angular resolution. We introduce the polar coordinate representation and describe a family of algorithms which use polar representation. The...
Duncan, Christian A., Efrat, Alon, Kobourov, Stephen G., Wenk, Carola
In this paper, we introduce the problem of drawing with "fat" edges. Traditionally, graph drawing algorithms represent vertices as circles and edges as closed curves connecting the vertices. In this...
Polar Coordinate Drawing of Planar Graphs with Good Angular Resolution (2002)
Duncan, Christian A., Kobourov, Stephen G.
We present a novel way to draw planar graphs with good angular resolution. We introduce the polar coordinate representation and describe a family of algorithms which use polar representation. The...
Duncan, Christian A., Efrat, Alon, Kobourov, Stephen G., Wenk, Carola
In this paper, we introduce the problem of drawing with "fat" edges. Traditionally, graph drawing algorithms represent vertices as circles and edges as closed curves connecting the vertices. In this...
Polar coordinate drawing of planar graphs with good angular resolution (2002)
Christian A. Duncan, Stephen G. Kobourov
We present a novel way to draw planar graphs with good angular resolution. We introduce the polar coordinate representation and describe a family of algorithms for constructing it. The main advantage...
Optimal constrained graph exploration (2001)
Christian A. Duncan, Stephen G. Kobourov
We address the problem of exploring an unknown graph G = (V; E) from a given start node s with either a tethered robot or a robot with fuel tank of limited fuel capacity, the former being a tighter...
Optimal constrained graph exploration (2001)
Christian A. Duncan, Stephen G. Kobourov
We address the problem of exploring an unknown graph G = (V; E) from a given start node s with either a tethered robot or a robot with a fuel tank of limited capacity, the former being a tighter...
Christian A. Duncan, Alon Efrat, Stephen G. Kobourov, Carola Wenk
Abstract. In this paper, we introduce the problem of drawing with “fat ” edges. Traditionally, graph drawing algorithms represent vertices as circles and edges as closed curves connecting the...
Efficient perspective-accurate silhouette computation and applications (2001)
Mihai Pop, Christian A. Duncan, Gill Barequet, Michael T. Goodrich, Wenjing Huang
� � � � � �Æ � � � � � � � � � � � ��Æ � � � � � � � � �Æ � � � � � � � �Æ � � � � � � � � � � � �...
K-D Trees Are Better when Cut on the Longest Side (2000)
Matthew Dickerson, Christian A. Duncan, Michaelt. Goodrich
Abstract. We show that a popular variant of the well known k-d tree data structure satisfies an important packing lemma. This variant is a binary spatial partitioning tree T defined on a set of n...
Drawing Planar Graphs with Circular Arcs (1999)
Cheng, C. C., Duncan, Christian A., Goodrich, Michael T., Kobourov, Stephen G.
In this paper we address the problem of drawing planar graphs with circular arcs while maintaining good angular resolution and small drawing area. We present a lower bound on the area of drawings in...
Planarity-Preserving Clustering and Embedding for Large Planar Graphs (1999)
Duncan, Christian A., Goodrich, Michael T., Kobourov, Stephen G.
In this paper we present a novel approach for cluster-based drawing of large planar graphs that maintains planarity. Our technique works for arbitrary planar graphs and produces a clustering which...
Drawing Planar Graphs with Circular Arcs (1999)
Cheng, C. C., Duncan, Christian A., Goodrich, Michael T., Kobourov, Stephen G.
In this paper we address the problem of drawing planar graphs with circular arcs while maintaining good angular resolution and small drawing area. We present a lower bound on the area of drawings in...
Planarity-Preserving Clustering and Embedding for Large Planar Graphs (1999)
Duncan, Christian A., Goodrich, Michael T., Kobourov, Stephen G.
In this paper we present a novel approach for cluster-based drawing of large planar graphs that maintains planarity. Our technique works for arbitrary planar graphs and produces a clustering which...
Drawing Planar Graphs with Circular Arcs (1999)
Cheng, C. C., Duncan, Christian A., Goodrich, Michael T., Kobourov, Stephen G.
In this paper we address the problem of drawing planar graphs with circular arcs while maintaining good angular resolution and small drawing area. We present a lower bound on the area of drawings in...
Planarity-Preserving Clustering and Embedding for Large Planar Graphs (1999)
Duncan, Christian A., Goodrich, Michael T., Kobourov, Stephen G.
In this paper we present a novel approach for cluster-based drawing of large planar graphs that maintains planarity. Our technique works for arbitrary planar graphs and produces a clustering which...
Geomnet: Geometric computing over the internet (1999)
Gill Barequet, Christian A. Duncan, T. Goodrich, Stina S. Bridgeman, Roberto Tamassia
GeomNet’s layered client-server architecture lets users perform distributed geometric computing over the Internet without having to download, install, and interface with software.
Planarity-preserving clustering and embedding for large planar graphs (1999)
Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov
Abstract. In this paper we present a novel approach for cluster-based drawing of large planar graphs that maintains planarity. Our technique works for arbitrary planar graphs and produces a...
Planarity-preserving clustering and embedding for large planar graphs (1999)
Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov
Abstract. In this paper we present a novel approach for cluster-based drawing of large planar graphs that maintains planarity. Our technique works for arbitrary planar graphs and produces a...
Balanced Aspect Ratio Trees: Combining the Advantages of (1999)
Trees And Octrees, Christian A. Duncan, Michael T. Goodrich, Stephen Kobourov
Given a set S of n points in IR d , we show, for fixed d, how to construct in O(n log n) time a data structure we call the Balanced Aspect Ratio (BAR) tree. A BAR tree is a binary space partition...
Balanced Aspect Ratio Trees: Combining the Advantages of k-d Trees and Octrees (1999)
Christian A. Duncan, Michael T. Goodrich, Stephen Kobourov
Given a set S of n points in IR d , we show, for fixed d, how to construct in O(n log n) time a data structure we call the Balanced Aspect Ratio (BAR) tree. A BAR tree is a binary space partition...
Balanced Aspect Ratio Trees: Combining the Advantages of k-d Trees and Octrees (1999)
Christian A. Duncan, Michael T. Goodrich, Stephen Kobourov
Given a set S of n points in IR d , we show, for fixed d, how to construct in O(n log n) time a data structure we call the Balanced Aspect Ratio (BAR) tree. A BAR tree is a binary space partition...
Ecient Perspective-Accurate Silhouette Computation (1999)
Gill Barequet Christian, Christian A. Duncan, Michael T. Goodrich, Wenjing Huang
Silhouettes are perceptually and geometrically salient features of geometric models. Hence a number of graphics and visualization applications need to nd them to aid further processing. The ecient...
Balanced aspect ratio trees: Combining the advantages of k-d trees and octrees (1999)
Christian A. Duncan, Michael T. Goodrich, Stephen Kobourov
Given a set S of n points on � d, we show, for fixed d, how to construct in Onlog Ž n. time a data structure we call the balanced aspect ratio Ž BAR. tree. A BAR tree is a binary space partition...
Planarity-preserving clustering and embedding for large planar graphs (1999)
Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov
Abstract. In this paper we present a novel approach for cluster-based drawing of large planar graphs that maintains planarity. Our technique works for arbitrary planar graphs and produces a...
Balanced Aspect Ratio Trees and Their Use for Drawing Very Large Graphs (1998)
Duncan, Christian A., Goodrich, Michael T., Kobourov, Stephen G.
We describe a new approach for cluster-based drawing of very large graphs, which obtains clusters by using binary space partition (BSP) trees. We also introduce a novel BSP-type decomposition, called...
Balanced Aspect Ratio Trees and Their Use for Drawing Very Large Graphs (1998)
Duncan, Christian A., Goodrich, Michael T., Kobourov, Stephen G.
We describe a new approach for cluster-based drawing of very large graphs, which obtains clusters by using binary space partition (BSP) trees. We also introduce a novel BSP-type decomposition, called...
Balanced Aspect Ratio Trees and Their Use for Drawing Very Large Graphs (1998)
Duncan, Christian A., Goodrich, Michael T., Kobourov, Stephen G.
We describe a new approach for cluster-based drawing of very large graphs, which obtains clusters by using binary space partition (BSP) trees. We also introduce a novel BSP-type decomposition, called...
Balanced Aspect Ratio Trees and Their Use for Drawing Very Large Graphs (1998)
Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov
We describe a new approach for cluster-based drawing of large graphs, which obtains clusters by using binary space partition (BSP) trees. We also introduce a novel BSP-type decomposition, called the...
Balanced Aspect Ratio Trees and Their Use for Drawing Very Large Graphs (1998)
Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov
Abstract. We describe a new approach for cluster-based drawing of very large graphs, which obtains clusters by using binary space partition (BSP) trees. We also introduce a novel BSP-type...
RSVP: A Geometric Toolkit for Controlled Repair of Solid Models (1998)
Gill Barequet, Christian A. Duncan, Subodh Kumar
This paper presents a system and the associated algorithms for repairing the boundary representation of CAD models. Two types of errors are considered: topological errors, i.e., aggregate errors like...
Balanced Aspect Ratio Trees and Their Use for Drawing Very Large Graphs (1998)
Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov
We describe a new approach for cluster-based drawing of large graphs, which obtains clusters by using binary space partition (BSP) trees. We also introduce a novel BSP-type decomposition, called the...
Balanced Aspect Ratio Trees and Their Use for Drawing Large Graphs (1998)
Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov
We describe a new approach for cluster-based drawing of large graphs, which obtains clusters by using binary space partition (BSP) trees. We also introduce a novel BSP-type decomposition, called the...
Balanced Aspect Ratio Trees and Their Use for Drawing Very Large Graphs (1998)
Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov
We describe a new approach for cluster-based drawing of very large graphs, which obtains clusters by using binary space partition (BSP) trees. We also introduce a novel BSP-type decomposition, called...
RSVP: A Geometric Toolkit for Controlled Repair of Solid Models (1998)
Gill Barequet Christian, Christian A. Duncan, Subodh Kumar
This paper presents a system and the associated algorithms for repairing the boundary representation of CAD models. Two types of errors are considered: topological errors, i.e., aggregate errors like...
Balanced Aspect Ratio Trees and Their Use for Drawing Very Large Graphs (1998)
Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov
Abstract. We describe a new approach for cluster-based drawing of very large graphs, which obtains clusters by using binary space partition (BSP) trees. We also introduce a novel BSP-type...
Efficient approximation and optimization algorithms for computational metrology (1997)
Christian A. Duncan, Michael T. Goodrich, Edgar A. Ramos
We give efficient algorithms for solving several geometric problems in computational metrology, focusing on the fundamental issues of "flatness " and "roundness. "...
Classical Computational Geometry in GeomNet (1997)
Gill Barequet, Stina S. Bridgeman, Christian A. Duncan, Michael T. Goodrich, Roberto Tamassia
In this paper we present GeomNet, a system for performing distributed geometric computing over the Internet. We also provide several examples of actual geometric algorithms that our system already...
Efficient Approximation and Optimization Algorithms for Computational Metrology (1997)
Christian A. Duncan, Michael T. Goodrich, Edgar A. Ramos
We give efficient algorithms for solving several geometric problems in computational metrology, focusing on the fundamental issues of "flatness" and "roundness." Specifically, we...