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...
GMap: Drawing Graphs as Maps (2009)
Gansner, Emden R., Hu, Yifan, Kobourov, Stephen G.
Information visualization is essential in making sense out of large data sets. Often, high-dimensional data are visualized as a collection of points in 2-dimensional space through dimensionality...
Upward Straight-Line Embeddings of Directed Graphs into Point Sets (2009)
Ro Estrella-balderrama, Fabrizio Frati, Stephen G. Kobourov
Abstract. In this paper we consider the problem of characterizing the directed graphs that admit an upward straight-line embedding into every point set in convex or in general position. In...
Graph Simultaneous Embedding Tool, GraphSET (2009)
Alejandro Estrella-Balderrama, J. Joseph Fowler, Stephen G. Kobourov
Problems in simultaneous graph drawing involve the layout of several graphs on a shared vertex set. This paper describes a Graph Simultaneous Embedding Tool, GraphSET, designed to allow the...
Morphing planar graphs in spherical space (2008)
Stephen G. Kobourov, Matthew L
Abstract. We consider the problem of intersection-free planar graph morphing, and in particular, a generalization from Euclidean space to spherical space. We show that under certain conditions, there...
Collaboration with diamondtouch (2008)
Stephen G. Kobourov, Kyriacos Pavlou, Mark Miles, A Wixted
Abstract. We study the performance of collaborative spatial/visual tasks under different input configurations. The configurations used are a traditional mouse-monitor, a shared-monitor with...
A force-directed approach to sensor localization (2008)
Alon Efrat, David Forrester, Stephen G. Kobourov, Cesim Erten
We consider the centralized, anchor-free sensor localization problem. We consider the case where the sensor network reports range information and the case where in addition to the range, we also have...
General Terms: Algorithms, Languages, Verification (2008)
Christian Collberg, Stephen G. Kobourov, Suzanne Westbrook
Graphical user interfaces
Collaboration with diamondtouch (2008)
Stephen G. Kobourov, Kyriacos Pavlou, Mark Miles, A Wixted
Abstract. We study the performance of collaborative spatial/visual tasks under different input configurations. The configurations used are a traditional mouse-monitor, a shared-monitor with...
Specialized Assignments Using L A T E (2008)
Michael T. Goodrich, Stephen G. Kobourov, Roberto Tamassia
Abstract We present SAIL, a package for the creation of Specialized Assignment In LATEX. We describe several features which allow an instructor to create sufficiently different instances of the...
Stephen G. Kobourov, Summa Cum Laude, Dartmouth College
Refereed Journal Publications (authors in alphabetical order)
Morphing planar graphs in spherical space (2008)
Stephen G. Kobourov, Matthew L
Abstract. We consider the problem of intersection-free planar graph morphing, and in particular, a generalization from Euclidean space to spherical space. We show that there exists a continuous and...
We present a method by which force-directed algorithms for graph layouts can be generalized to calculate the layout of a graph in an arbitrary Riemannian geometry. The method relies on extending the...
Computing Homotopic Shortest Paths Efficiently (2008)
Alon Efrat, Stephen G. Kobourov, Anna Lubiw
We give algorithms to find shortest paths homotopic to given disjoint paths that wind amongst n point obstacles in the plane. Our deterministic algorithm runs in time O(k log n+n √n), and...
Characterization of Unlabeled Level Planar Graphs (2008)
Fowler, J. Joseph, Kobourov, Stephen G.
We present the set of planar graphs that always have a simultaneous geometric embedding with a strictly monotone path on the same set of $n$ vertices, for any of the $n!$ possible mappings. These...
Constrained Simultaneous and Near-Simultaneous Embeddings (2008)
Frati, Fabrizio, Kaufmann, Michael, Kobourov, Stephen G.
A geometric simultaneous embedding of two graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ with a bijective mapping of their vertex sets $gamma : V_1 rightarrow V_2$ is a pair of planar straight-line...
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...
Minimum Level Nonplanar Patterns for Trees (2008)
Fowler, J. Joseph, Kobourov, Stephen G.
Minimum lvel nonplanar (MLNP) patterns play the role for level planar graphs that the forbidden Kuratowksi subdivisions $K_5$ and $K_3,3$ play for planar graphs. We add two MLNP patterns for trees to...
Characterization of Unlabeled Level Planar Graphs (2008)
Fowler, J. Joseph, Kobourov, Stephen G.
We present the set of planar graphs that always have a simultaneous geometric embedding with a strictly monotone path on the same set of $n$ vertices, for any of the $n!$ possible mappings. These...
Constrained Simultaneous and Near-Simultaneous Embeddings (2008)
Frati, Fabrizio, Kaufmann, Michael, Kobourov, Stephen G.
A geometric simultaneous embedding of two graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ with a bijective mapping of their vertex sets $gamma : V_1 rightarrow V_2$ is a pair of planar straight-line...
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...
Minimum Level Nonplanar Patterns for Trees (2008)
Fowler, J. Joseph, Kobourov, Stephen G.
Minimum lvel nonplanar (MLNP) patterns play the role for level planar graphs that the forbidden Kuratowksi subdivisions $K_5$ and $K_3,3$ play for planar graphs. We add two MLNP patterns for trees to...
GRIP: Graph dRawing with Intelligent Placement (2007)
Short System Demonstration, Pawel Gajer, Stephen G. Kobourov
This paper describes a system for Graph dRawing with Intelligent Placement, GRIP. The GRIP system is designed for drawing large graphs and uses a novel multi-dimensional force-directed method...
esidential Scholar 1994-95: independent project on a DECmpp parallel machine ffl Rufus Choate Scholar 1992-1994 ffl Waterhouse Fellow 1994 ffl Honorarium Scholarship of the Sofia University 1992-1995...
VLGD, Algorithm for Drawing Very Large Graphs (2007)
Michael Goodrich, Stephen G. Kobourov
Given a large planar graph we want to display it in a meaningful fashion. We present VLGD: a new, straightforward and fast algorithm for automatic display of very large planar graphs. We recursively...
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...
Simultaneous Graph Embedding with Bends and Circular Arcs (2007)
Cappos, Justin, Estrella-Balderrama, Alejandro, Fowler, J. Joseph, Kobourov, Stephen G.
We consider the problem of simultaneous embedding of planar graphs. We demonstrate how to simultaneously embed a path and an n-level planar graph and how to use radial embeddings for curvilinear...
Morphing Planar Graphs in Spherical Space (2007)
Kobourov, Stephen G., Landis, Matthew
We consider the problem of intersection-free planar graph morphing, and in particular, a generalization from Euclidean space to spherical space. We show that there exists a continuous and...
Characterization of Unlabeled Level Planar (ULP) Trees (2007)
Estrella-Balderrama, Alejandro, Fowler, J. Joseph, Kobourov, Stephen G.
Consider a graph G drawn in the plane so that each vertex lies on a distinct horizontal line $\ell_j = \{(x, j) \,|\, x \in \BB{R}\}$. The bijection $\phi$ that maps the set of n vertices V to a set...
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...
Simultaneous Graph Embedding with Bends and Circular Arcs (2007)
Cappos, Justin, Estrella-Balderrama, Alejandro, Fowler, J. Joseph, Kobourov, Stephen G.
We consider the problem of simultaneous embedding of planar graphs. We demonstrate how to simultaneously embed a path and an n-level planar graph and how to use radial embeddings for curvilinear...
Morphing Planar Graphs in Spherical Space (2007)
Kobourov, Stephen G., Landis, Matthew
We consider the problem of intersection-free planar graph morphing, and in particular, a generalization from Euclidean space to spherical space. We show that there exists a continuous and...
Characterization of Unlabeled Level Planar (ULP) Trees (2007)
Estrella-Balderrama, Alejandro, Fowler, J. Joseph, Kobourov, Stephen G.
Consider a graph G drawn in the plane so that each vertex lies on a distinct horizontal line $\ell_j = \{(x, j) \,|\, x \in \BB{R}\}$. The bijection $\phi$ that maps the set of n vertices V to a set...
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...
Colored Simultaneous Geometric Embeddings (2007)
Brandes, Ulrik, Erten, Cesim, Fowler, J. Joseph, Frati, Fabrizio, Geyer, Markus, Gutwenger, Carsten, ...
We introduce the concept of colored simultaneous geometric embeddings as a generalization of simultaneous graph embeddings with and without mapping. We show that there exists a universal pointset of...
Minimum level nonplanar patterns for trees (2007)
J. Joseph Fowler, Stephen G. Kobourov
Abstract. We add two minimum level nonplanar (MLNP) patterns for trees to the previous set of tree patterns given by Healy et al. [3]. Neither of these patterns match any of the previous patterns. We...
Article Type Communicated by Submitted Revised (2007)
Stephen G. Kobourov, Matthew Landis
We consider the problem of intersection-free planar graph morphing, and in particular, a generalization from Euclidean space to spherical space. We show that there exists a continuous and...
Simultaneous graph embedding with bends and circular arcs (2006)
Ro Estrella-balderrama, J. Joseph Fowler, Stephen G. Kobourov
Abstract. We consider the problem of simultaneous embedding of planar graphs. We demonstrate how to simultaneously embed a path and an n-level planar graph and how to use radial embeddings for...
Characterization of unlabeled level planar trees (2006)
Ro Estrella-balderrama, J. Joseph Fowler, Stephen G. Kobourov
Abstract. Consider a graph G drawn in the plane so that each vertex lies on a distinct horizontal line ℓj = {(x, j) | x ∈ R}. The bijection φ that maps the set of n vertices V to a set of...
Characterization of unlabeled level planar graphs (2006)
J. Joseph Fowler, Stephen G. Kobourov
Abstract. We present the set of planar graphs that always have a simultaneous geometric embedding with a strictly monotonic path on the same set of n vertices, for any of the n! possible mappings....
Characterization of unlabeled level planar trees (2006)
Ro Estrella-balderrama, J. Joseph Fowler, Stephen G. Kobourov
Abstract. Consider a graph G drawn in the plane so that each vertex lies on a distinct horizontal line ℓj = {(x, j) | x ∈ R}. The bijection φ that maps the set of n vertices V to a set of...
Simultaneous graph embedding with bends and circular arcs (2006)
Ro Estrella-balderrama, J. Joseph Fowler, Stephen G. Kobourov
Abstract. We consider the problem of simultaneous embedding of planar graphs. We demonstrate how to simultaneously embed a path and an n-level planar graph and how to use radial embeddings for...
Characterization of unlabeled level planar graphs (2006)
J. Joseph Fowler, Stephen G. Kobourov
Abstract. We present the set of planar graphs that always have a simultaneous geometric embedding with a strictly monotonic path on the same set of n vertices, for any of the n! possible mappings....
Force-Directed Approaches to Sensor Network Localization (2006)
Kobourov, Stephen G., Efrat, Alon, Forrester, David, Iyer, Anand
In many sensor network applications it is necessary to compute low-error localization of the sensor nodes. Although embedding a GPS unit on each node would solve the problem for many outdoor...
GraphAEL: Graph Animations with Evolving Layouts (2004)
Erten, Cesim, Harding, Philipp J., Kobourov, Stephen G., Wampler, Kevin, Yee, Gary V.
GraphAEL extracts three types of evolving graphs from the Graph Drawing literature and creates 2D and 3D animations of the evolutions. We study citation graphs, topic graphs, and collaboration...
Fixed-Location Circular-Arc Drawing of Planar Graphs (2004)
Efrat, Alon, Erten, Cesim, Kobourov, Stephen G.
In this paper we consider the problem of drawing a planar graph using circular-arcs as edges, given a one-to-one mapping between the vertices of the graph and a set of n points on the plane, where n...
Intersection-Free Morphing of Planar Graphs (2004)
Erten, Cesim, Kobourov, Stephen G., Pitta, Chandan
Given two different drawings of a planar graph we consider the problem of morphing one drawing into the other. We designed and implemented an algorithm for intersection-free morphing of planar...
Simultaneous Graph Drawing: Layout Algorithms and Visualization Schemes (2004)
Erten, Cesim, Kobourov, Stephen G., Le, Vu, Navabi, Armand
In this paper we consider the problem of drawing and displaying a series of related graphs, i.e., graphs that share all, or parts of the same vertex set. We designed and implemented three different...
Selected Open Problems in Graph Drawing (2004)
Brandenburg, Franz J., Eppstein, David, Goodrich, Michael T., Kobourov, Stephen G., Liotta, Giuseppe, Mutzel, Petra
In this manuscript, we present several challenging and interesting open problems in graph drawing. The goal of the listing in this paper is to stimulate future research in graph drawing.
Simultaneous Embedding of Planar Graphs with Few Bends (2004)
Erten, Cesim, Kobourov, Stephen G.
We present an O(n) time algorithm for simultaneous embedding of pairs of planar graphs on the O(n^2)× O(n^2) grid, with at most three bends per edge, where n is the number of vertices. For the case...
Visualizing Large Graphs with Compound-Fisheye Views and Treemaps (2004)
Abello, James, Kobourov, Stephen G., Yusufov, Roman
Compound-fisheye views are introduced as a method for the display and interaction with large graphs. The method relies on a hierarchical clustering of the graph, and a generalization of the...
Graphael: A System for Generalized Force-Directed Layouts (2004)
Forrester, David, Kobourov, Stephen G., Navabi, Armand, Wampler, Kevin, Yee, Gary V.
The graphael system implements several traditional force-directed layout methods, as well as several novel layout methods for non-Euclidean geometries, including hyperbolic and spherical. The system...
An Interactive Multi-user System for Simultaneous Graph Drawing (2004)
Kobourov, Stephen G., Pitta, Chandan
In this paper we consider the problem of simultaneous drawing of two graphs. The goal is to produce aesthetically pleasing drawings for the two graphs by means of a heuristic algorithm and with human...
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...
GraphAEL: Graph Animations with Evolving Layouts (2004)
Erten, Cesim, Harding, Philipp J., Kobourov, Stephen G., Wampler, Kevin, Yee, Gary V.
GraphAEL extracts three types of evolving graphs from the Graph Drawing literature and creates 2D and 3D animations of the evolutions. We study citation graphs, topic graphs, and collaboration...
Fixed-Location Circular-Arc Drawing of Planar Graphs (2004)
Efrat, Alon, Erten, Cesim, Kobourov, Stephen G.
In this paper we consider the problem of drawing a planar graph using circular-arcs as edges, given a one-to-one mapping between the vertices of the graph and a set of n points on the plane, where n...
Intersection-Free Morphing of Planar Graphs (2004)
Erten, Cesim, Kobourov, Stephen G., Pitta, Chandan
Given two different drawings of a planar graph we consider the problem of morphing one drawing into the other. We designed and implemented an algorithm for intersection-free morphing of planar...
Simultaneous Graph Drawing: Layout Algorithms and Visualization Schemes (2004)
Erten, Cesim, Kobourov, Stephen G., Le, Vu, Navabi, Armand
In this paper we consider the problem of drawing and displaying a series of related graphs, i.e., graphs that share all, or parts of the same vertex set. We designed and implemented three different...
Selected Open Problems in Graph Drawing (2004)
Brandenburg, Franz J., Eppstein, David, Goodrich, Michael T., Kobourov, Stephen G., Liotta, Giuseppe, Mutzel, Petra
In this manuscript, we present several challenging and interesting open problems in graph drawing. The goal of the listing in this paper is to stimulate future research in graph drawing.
Simultaneous Embedding of Planar Graphs with Few Bends (2004)
Erten, Cesim, Kobourov, Stephen G.
We present an O(n) time algorithm for simultaneous embedding of pairs of planar graphs on the O(n^2)× O(n^2) grid, with at most three bends per edge, where n is the number of vertices. For the case...
Visualizing Large Graphs with Compound-Fisheye Views and Treemaps (2004)
Abello, James, Kobourov, Stephen G., Yusufov, Roman
Compound-fisheye views are introduced as a method for the display and interaction with large graphs. The method relies on a hierarchical clustering of the graph, and a generalization of the...
Graphael: A System for Generalized Force-Directed Layouts (2004)
Forrester, David, Kobourov, Stephen G., Navabi, Armand, Wampler, Kevin, Yee, Gary V.
The graphael system implements several traditional force-directed layout methods, as well as several novel layout methods for non-Euclidean geometries, including hyperbolic and spherical. The system...
An Interactive Multi-user System for Simultaneous Graph Drawing (2004)
Kobourov, Stephen G., Pitta, Chandan
In this paper we consider the problem of simultaneous drawing of two graphs. The goal is to produce aesthetically pleasing drawings for the two graphs by means of a heuristic algorithm and with human...
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...
GraphAEL: Graph Animations with Evolving Layouts (2004)
Erten, Cesim, Harding, Philipp J., Kobourov, Stephen G., Wampler, Kevin, Yee, Gary V.
GraphAEL extracts three types of evolving graphs from the Graph Drawing literature and creates 2D and 3D animations of the evolutions. We study citation graphs, topic graphs, and collaboration...
Fixed-Location Circular-Arc Drawing of Planar Graphs (2004)
Efrat, Alon, Erten, Cesim, Kobourov, Stephen G.
In this paper we consider the problem of drawing a planar graph using circular-arcs as edges, given a one-to-one mapping between the vertices of the graph and a set of n points on the plane, where n...
Intersection-Free Morphing of Planar Graphs (2004)
Erten, Cesim, Kobourov, Stephen G., Pitta, Chandan
Given two different drawings of a planar graph we consider the problem of morphing one drawing into the other. We designed and implemented an algorithm for intersection-free morphing of planar...
Simultaneous Graph Drawing: Layout Algorithms and Visualization Schemes (2004)
Erten, Cesim, Kobourov, Stephen G., Le, Vu, Navabi, Armand
In this paper we consider the problem of drawing and displaying a series of related graphs, i.e., graphs that share all, or parts of the same vertex set. We designed and implemented three different...
Selected Open Problems in Graph Drawing (2004)
Brandenburg, Franz J., Eppstein, David, Goodrich, Michael T., Kobourov, Stephen G., Liotta, Giuseppe, Mutzel, Petra
In this manuscript, we present several challenging and interesting open problems in graph drawing. The goal of the listing in this paper is to stimulate future research in graph drawing.
Simultaneous Embedding of Planar Graphs with Few Bends (2004)
Erten, Cesim, Kobourov, Stephen G.
We present an O(n) time algorithm for simultaneous embedding of pairs of planar graphs on the O(n^2)× O(n^2) grid, with at most three bends per edge, where n is the number of vertices. For the case...
Visualizing Large Graphs with Compound-Fisheye Views and Treemaps (2004)
Abello, James, Kobourov, Stephen G., Yusufov, Roman
Compound-fisheye views are introduced as a method for the display and interaction with large graphs. The method relies on a hierarchical clustering of the graph, and a generalization of the...
Graphael: A System for Generalized Force-Directed Layouts (2004)
Forrester, David, Kobourov, Stephen G., Navabi, Armand, Wampler, Kevin, Yee, Gary V.
The graphael system implements several traditional force-directed layout methods, as well as several novel layout methods for non-Euclidean geometries, including hyperbolic and spherical. The system...
An Interactive Multi-user System for Simultaneous Graph Drawing (2004)
Kobourov, Stephen G., Pitta, Chandan
In this paper we consider the problem of simultaneous drawing of two graphs. The goal is to produce aesthetically pleasing drawings for the two graphs by means of a heuristic algorithm and with human...
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...
Simultaneous embedding of planar graphs with few bends (2004)
Cesim Erten, Stephen G. Kobourov
We consider several variations of the simultaneous embedding problem for planar graphs. We begin with a simple proof that not all pairs of planar graphs have simultaneous geometric embedding....
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...
Simultaneous embedding of planar graphs with few bends (2004)
Cesim Erten, Stephen G Kobourov
Abstract. We present an O(n) time algorithm for simultaneous embedding of pairs of planar graphs on the O(n 2)×O(n 2) grid, with at most three bends per edge, where n is the number of vertices. For...
An interactive multi-user system for simultaneous graph drawing (2004)
Abstract. In this paper we consider the problem of simultaneous drawing of two graphs. The goal is to produce aesthetically pleasing drawings for the two graphs by means of a heuristic algorithm and...
Visualizing large graphs with compound-fisheye views and treemaps (2004)
James Abello, Stephen G. Kobourov, Roman Yusufov
Abstract. Compound-fisheye views are introduced as a method for the display and interaction with large graphs. The method relies on a hierarchical clustering of the graph, and a generalization of the...
Simultaneous embedding of planar graphs with few bends (2004)
Cesim Erten, Stephen G. Kobourov
We consider several variations of the simultaneous embedding problem for planar graphs. We begin with a simple proof that not all pairs of planar graphs have simultaneous geometric embeddings....
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...
Intersection-free morphing of planar graphs (2003)
Cesim Erten, Stephen G. Kobourov, An Pitta
Abstract. Given two different drawings of a planar graph we consider the problem of morphing one drawing into the other. We designed and implemented an algorithm for intersection-free morphing of...
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...
Optimal Strategies to Track and Capture a Predictable Target (2003)
Alon Efrat Ector, Alon Efrat, Stephen G. Kobourov
We present an O(n log for computing the optimal robot motion that maintains lineof -sight visibility between a target moving inside a polygon with n vertices which may contain holes. The motion is...
Fixed-location circular-arc drawing of planar graphs (2003)
Alon Efrat, Cesim Erten, Stephen G. Kobourov
Abstract. In this paper we consider the problem of drawing a planar graph using circular-arcs as edges and given a one-to-one mapping between the vertices of the graph and a set of n points on the...
Fixed-location circular-arc drawing of planar graphs (2003)
Alon Efrat, Cesim Erten, Stephen G. Kobourov
In this paper we consider the problem of drawing a planar graph using circular arcs as edges, given a one-to-one mapping between the vertices of the graph and a set of points in the plane. If for...
Computing Homotopic Shortest Paths Efficiently (2002)
Efrat, Alon, Kobourov, Stephen G., Lubiw, Anna
This paper addresses the problem of finding shortest paths homotopic to a given disjoint set of paths that wind amongst point obstacles in the plane. We present a faster algorithm than previously...
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...
Simultaneous Embedding of a Planar Graph and Its Dual on the Grid (2002)
Cesim Erten, Stephen G. Kobourov
Traditional representations of graphs and their duals suggest the requirement that the dual vertices should be placed inside their corresponding primal faces, and the edges of the dual graph should...
Computing homotopic shortest paths efficiently (2002)
Alon Efrat, Stephen G. Kobourov, Anna Lubiw
Geometric shortest paths are a major topic in computational geometry; see the survey paper by Mitchell [12]. A shortest path between two points in a simple polygon can be found in linear time using...
Simultaneous embedding of a planar graph and its dual on the grid (2002)
Cesim Erten, Stephen G. Kobourov
Abstract. Traditional representations of graphs and their duals suggest the requirement that the dual vertices should be placed inside their corresponding primal faces, and the edges of the dual...
A Multi-dimensional Approach to Force-Directed Layouts of Large Graphs (2001)
Gajer, Pawel, Goodrich, Michael T., Kobourov, Stephen G.
We present a novel hierarchical force-directed method for drawing large graphs. The algorithm produces a graph embedding in an Euclidean space \mathbb{E} of any dimension. A two or three dimensional...
A Multi-dimensional Approach to Force-Directed Layouts of Large Graphs (2001)
Gajer, Pawel, Goodrich, Michael T., Kobourov, Stephen G.
We present a novel hierarchical force-directed method for drawing large graphs. The algorithm produces a graph embedding in an Euclidean space \mathbb{E} of any dimension. A two or three dimensional...
A Multi-dimensional Approach to Force-Directed Layouts of Large Graphs (2001)
Gajer, Pawel, Goodrich, Michael T., Kobourov, Stephen G.
We present a novel hierarchical force-directed method for drawing large graphs. The algorithm produces a graph embedding in an Euclidean space \mathbb{E} of any dimension. A two or three dimensional...
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...
A Multi-dimensional Approach to Force-Directed Layouts of Large Graphs (2000)
Pawel Gajer, Michael T. Goodrich, Stephen G. Kobourov
Abstract. We present a novel hierarchical force-directed method for drawing large graphs. The algorithm produces a graph embedding in an Euclidean space E of any dimension. A two or three dimensional...
A fast multi-dimensional algorithm for drawing large graphs (2000)
Pawel Gajer, Michael T. Goodrich, Stephen G. Kobourov
We present a novel hierarchical force-directed method for drawing large graphs. The algorithm produces a graph embedding in an Euclidean space E of any dimension. A two or three dimensional drawing...
A fast multi-dimensional algorithm for drawing large graphs (2000)
Pawel Gajer, Michael T. Goodrich, Stephen G. Kobourov
We present a novel hierarchical force-directed method for drawing large graphs. The algorithm produces a graph embedding in an Euclidean space E of any dimension. A two or three dimensional drawing...
A System for Generating, Archiving, and Retrieving Specialized Assignments Using LATEX (2000)
Stina Bridgeman, Michael T. Goodrich, Stephen G. Kobourov, Roberto Tamassia
We present SAIL, a package for the creation of Specialized Assignment In L A T E X. We describe several features which allow an instructor to create su- ciently dierent instances of the \same"...
PILOT: An Interactive Tool for Learning and Grading (2000)
Stina Bridgeman, Michael T. Goodrich, Stephen G. Kobourov, Roberto Tamassia
We describe a Web-based interactive tool, called PILOT, for testing computer science concepts. The strengths of our system are its universal access and platform independence, its ability to test...
Grip: Graph drawing with intelligent placement (2000)
Pawel Gajer, Stephen G. Kobourov
Abstract. This paper describes a system for Graph dRawing with Intelligent Placement, GRIP. TheGRIP system is designed for drawing large graphs and uses a novel multi-dimensional force-directed...
A fast multi-dimensional algorithm for drawing large graphs (2000)
Pawel Gajer, Michael T. Goodrich, Stephen G. Kobourov
Abstract. We present a novel hierarchical force-directed method for drawing large graphs. The algorithm produces a graph embedding in an Euclidean space � of any dimension. A two or three...
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...
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...
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...
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...
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...