Universal Sets of n Points for One-bend Drawings of Planar Graphs with n Vertices (2009)
Everett, Hazel, Lazard, Sylvain, Liotta, Giuseppe, Wismath, Steve
This paper shows that any planar graph with $n$ vertices can be point-set embedded with at most one bend per edge on a universal set of n points in the plane. An implication of this result is that...
Universal Sets of n Points for One-bend Drawings of Planar Graphs with n Vertices (2009)
Everett, Hazel, Lazard, Sylvain, Liotta, Giuseppe, Wismath, Steve
This paper shows that any planar graph with $n$ vertices can be point-set embedded with at most one bend per edge on a universal set of n points in the plane. An implication of this result is that...
Point-Set Embedding of Trees with Edge Constraints (2008)
Di Giacomo, Emilio, Didimo, Walter, Liotta, Giuseppe, Meijer, Henk, Wismath, Stephen
Given a graph $G$ with $n$ vertices and a set $S$ of $n$ points in the plane, a $point-set embedding$ of $G$ on $S$ is a planar drawing such that each vertex of $G$ is mapped to a distinct point of...
Matched Drawings of Planar Graphs (2008)
Di Giacomo, Emilio, Didimo, Walter, Van Kreveld, Marc, Liotta, Giuseppe, Speckmann, Bettina
A natural way to draw two planar graphs whose vertex sets are matched is to assign each matched pair a unique $y$-coordinate. In this paper we introduce the concept of such matched drawings, which...
Drawing Colored Graphs with Contrained Vertex Positions and Few Bends per Edge (2008)
Di Giacomo, Emilio, Liotta, Giuseppe, Trotta, Francesco
Hamiltonicity, book embeddability, and point-set embeddability of planar graphs are strictly related concepts. We exploit the interplay between these notions to describe colored sets of points and to...
Universal Sets of n Points for 1-bend Drawings of Planar Graphs with n Vertices (2008)
Everett, Hazel, Lazard, Sylvain, Liotta, Giuseppe, Wismath, Stephen
This paper shows that any planar graph with $n$ vertices can be point-set embedded with at most one bend per edge on a universal set of $n$ points in the plane. An implication of this result is that...
Universal Sets of $n$ Points for 1-bend Drawings of Planar Graphs with $n$ Vertices (2008)
Everett, Hazel, Lazard, Sylvain, Liotta, Giuseppe, Wismath, Steve
This paper shows that any planar graph with $n$ vertices can be point-set embedded with at most one bend per edge on a universal set of $n$ points in the plane. An implication of this result is that...
Universal Sets of $n$ Points for 1-bend Drawings of Planar Graphs with $n$ Vertices (2008)
Everett, Hazel, Lazard, Sylvain, Liotta, Giuseppe, Wismath, Steve
This paper shows that any planar graph with $n$ vertices can be point-set embedded with at most one bend per edge on a universal set of $n$ points in the plane. An implication of this result is that...
Point-Set Embedding of Trees with Edge Constraints (2008)
Di Giacomo, Emilio, Didimo, Walter, Liotta, Giuseppe, Meijer, Henk, Wismath, Stephen
Given a graph $G$ with $n$ vertices and a set $S$ of $n$ points in the plane, a $point-set embedding$ of $G$ on $S$ is a planar drawing such that each vertex of $G$ is mapped to a distinct point of...
Matched Drawings of Planar Graphs (2008)
Di Giacomo, Emilio, Didimo, Walter, Van Kreveld, Marc, Liotta, Giuseppe, Speckmann, Bettina
A natural way to draw two planar graphs whose vertex sets are matched is to assign each matched pair a unique $y$-coordinate. In this paper we introduce the concept of such matched drawings, which...
Drawing Colored Graphs with Contrained Vertex Positions and Few Bends per Edge (2008)
Di Giacomo, Emilio, Liotta, Giuseppe, Trotta, Francesco
Hamiltonicity, book embeddability, and point-set embeddability of planar graphs are strictly related concepts. We exploit the interplay between these notions to describe colored sets of points and to...
Universal Sets of n Points for 1-bend Drawings of Planar Graphs with n Vertices (2008)
Everett, Hazel, Lazard, Sylvain, Liotta, Giuseppe, Wismath, Stephen
This paper shows that any planar graph with $n$ vertices can be point-set embedded with at most one bend per edge on a universal set of $n$ points in the plane. An implication of this result is that...
Drawable and Forbidden Minimum Weight Triangulations (Extended Abstract) (2007)
William Lenhart, Giuseppe Liotta
A graph is minimum weight drawable if it admits a straight-line drawing that is a minimum weight triangulation of the set of points representing the vertices of the graph. In this paper we consider...
k-colored point-set embeddability of outerplanar graphs (2007)
Wismath, Stephen K., Di Giacomo, Emilio, Didimo, Walter, Liotta, Giuseppe, Meijer, Henk, Trotta, Francesco
This paper addresses the problem of designing drawing algorithms that receive as input a planar graph $G$, a partitioning of the vertices of $G$ into $k$ different semantic categories $V_0, \cdots,...
Radial Drawings of Graphs: Geometric Constraints and Trade-offs (2007)
Di Giacomo, Emilio, Didimo, Walter, Liotta, Giuseppe
This paper studies how to compute radial drawings of graphs by taking into account additional geometric constraints which correspond to typical aesthetic and semantic requirements for the...
Drawing Bipartite Graphs on Two Curves (2007)
Di Giacomo, Emilio, Grilli, Luca, Liotta, Giuseppe
Let G be a bipartite graph, and let $\lambda_e,\lambda_i$ be two parallel convex curves; we study the question about whether G admits a planar straight line drawing such that the vertices of one...
k-colored point-set embeddability of outerplanar graphs (2007)
Wismath, Stephen K., Di Giacomo, Emilio, Didimo, Walter, Liotta, Giuseppe, Meijer, Henk, Trotta, Francesco
This paper addresses the problem of designing drawing algorithms that receive as input a planar graph $G$, a partitioning of the vertices of $G$ into $k$ different semantic categories $V_0, \cdots,...
Radial Drawings of Graphs: Geometric Constraints and Trade-offs (2007)
Di Giacomo, Emilio, Didimo, Walter, Liotta, Giuseppe
This paper studies how to compute radial drawings of graphs by taking into account additional geometric constraints which correspond to typical aesthetic and semantic requirements for the...
Drawing Bipartite Graphs on Two Curves (2007)
Di Giacomo, Emilio, Grilli, Luca, Liotta, Giuseppe
Let G be a bipartite graph, and let $\lambda_e,\lambda_i$ be two parallel convex curves; we study the question about whether G admits a planar straight line drawing such that the vertices of one...
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...
How to Embed a Path onto Two Sets of Points (2006)
Di Giacomo, Emilio, Liotta, Giuseppe, Trotta, Francesco
Let R and B be two sets of points such that the points of R are colored red and the points of B are colored blue. Let P be a path such that |R| vertices of P are red and |B| vertices of P are blue....
Upward Spirality and Upward Planarity Testing (2006)
Didimo, Walter, Giordano, Francesco, Liotta, Giuseppe
Let G be a digraph whose SPQR-tree does not have any R-node. The main result of this paper is a polynomial-time algorithm that tests whether G is upward planar and, if so, returns an upward planar...
Volume Requirements of 3D Upward Drawings (2006)
Di Giacomo, Emilio, Liotta, Giuseppe, Meijer, Henk
This paper studies the problem of drawing directed acyclic graphs in three dimensions in the straight-line grid model, and so that all directed edges are oriented in a common (upward) direction. We...
WhatsOnWeb: Using Graph Drawing to Search the Web (2006)
Di Giacomo, Emilio, Didimo, Walter, Grilli, Luca, Liotta, Giuseppe
One of the most challenging issues in mining information from the World Wide Web is the design of systems that can present the data to the end user by clustering them into meaningful semantic...
How to Embed a Path onto Two Sets of Points (2006)
Di Giacomo, Emilio, Liotta, Giuseppe, Trotta, Francesco
Let R and B be two sets of points such that the points of R are colored red and the points of B are colored blue. Let P be a path such that |R| vertices of P are red and |B| vertices of P are blue....
Upward Spirality and Upward Planarity Testing (2006)
Didimo, Walter, Giordano, Francesco, Liotta, Giuseppe
Let G be a digraph whose SPQR-tree does not have any R-node. The main result of this paper is a polynomial-time algorithm that tests whether G is upward planar and, if so, returns an upward planar...
Volume Requirements of 3D Upward Drawings (2006)
Di Giacomo, Emilio, Liotta, Giuseppe, Meijer, Henk
This paper studies the problem of drawing directed acyclic graphs in three dimensions in the straight-line grid model, and so that all directed edges are oriented in a common (upward) direction. We...
WhatsOnWeb: Using Graph Drawing to Search the Web (2006)
Di Giacomo, Emilio, Didimo, Walter, Grilli, Luca, Liotta, Giuseppe
One of the most challenging issues in mining information from the World Wide Web is the design of systems that can present the data to the end user by clustering them into meaningful semantic...
How to Embed a Path onto Two Sets of Points (2006)
Di Giacomo, Emilio, Liotta, Giuseppe, Trotta, Francesco
Let R and B be two sets of points such that the points of R are colored red and the points of B are colored blue. Let P be a path such that |R| vertices of P are red and |B| vertices of P are blue....
Upward Spirality and Upward Planarity Testing (2006)
Didimo, Walter, Giordano, Francesco, Liotta, Giuseppe
Let G be a digraph whose SPQR-tree does not have any R-node. The main result of this paper is a polynomial-time algorithm that tests whether G is upward planar and, if so, returns an upward planar...
Volume Requirements of 3D Upward Drawings (2006)
Di Giacomo, Emilio, Liotta, Giuseppe, Meijer, Henk
This paper studies the problem of drawing directed acyclic graphs in three dimensions in the straight-line grid model, and so that all directed edges are oriented in a common (upward) direction. We...
WhatsOnWeb: Using Graph Drawing to Search the Web (2006)
Di Giacomo, Emilio, Didimo, Walter, Grilli, Luca, Liotta, Giuseppe
One of the most challenging issues in mining information from the World Wide Web is the design of systems that can present the data to the end user by clustering them into meaningful semantic...
On embedding a graph on two sets of points (2005)
Emilio Di Giacomo, Emilio Di Giacomo, Giuseppe Liotta, Francesco Trotta, Francesco Trotta
Let R and B be two sets of points such that the points of R are colored red and the points of B are colored blue. Let G be a planar graph such that |R | vertices of G are red and |B | vertices of G...
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.
Computing Radial Drawings on the Minimum Number of Circles (2004)
Di Giacomo, Emilio, Didimo, Walter, Liotta, Giuseppe, Meijer, Henk
A radial drawing is a representation of a graph in which the vertices lie on concentric circles of finite radius. In this paper we study the problem of computing radial drawings of planar graphs by...
Hamiltonian-with-Handles Graphs and the k-Spine Drawability Problem (2004)
Di Giacomo, Emilio, Didimo, Walter, Liotta, Giuseppe, Suderman, Matthew
A planar graph G is k-spine drawable, k >= 0, if there exists a planar drawing of G in which each vertex of G lies on one of k horizontal lines, and each edge of G is drawn as a polyline consisting...
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.
Computing Radial Drawings on the Minimum Number of Circles (2004)
Di Giacomo, Emilio, Didimo, Walter, Liotta, Giuseppe, Meijer, Henk
A radial drawing is a representation of a graph in which the vertices lie on concentric circles of finite radius. In this paper we study the problem of computing radial drawings of planar graphs by...
Hamiltonian-with-Handles Graphs and the k-Spine Drawability Problem (2004)
Di Giacomo, Emilio, Didimo, Walter, Liotta, Giuseppe, Suderman, Matthew
A planar graph G is k-spine drawable, k >= 0, if there exists a planar drawing of G in which each vertex of G lies on one of k horizontal lines, and each edge of G is drawn as a polyline consisting...
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.
Computing Radial Drawings on the Minimum Number of Circles (2004)
Di Giacomo, Emilio, Didimo, Walter, Liotta, Giuseppe, Meijer, Henk
A radial drawing is a representation of a graph in which the vertices lie on concentric circles of finite radius. In this paper we study the problem of computing radial drawings of planar graphs by...
Hamiltonian-with-Handles Graphs and the k-Spine Drawability Problem (2004)
Di Giacomo, Emilio, Didimo, Walter, Liotta, Giuseppe, Suderman, Matthew
A planar graph G is k-spine drawable, k >= 0, if there exists a planar drawing of G in which each vertex of G lies on one of k horizontal lines, and each edge of G is drawn as a polyline consisting...
A Fixed-Parameter Approach to Two-Layer Planarization (2004)
Vida Dujmovic, Michael Fellows, Michael Hallett, Matthew Kitching, Giuseppe Liotta, Catherine Mccartin, ...
A bipartite graph is biplanar if the vertices can be placed on two parallel lines (layers) in the plane such that there are no edge crossings when edges are drawn as line segments between the layers....
Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions (2003)
Stefan Felsner, Giuseppe Liotta, Stephen Wismath
This paper investigates the following question: Given a grid ,where is a proper subset of the integer 2D or 3D grid, which graphs admit straight-line crossing-free drawings with vertices located at...
Optimal and Suboptimal Robust Algorithms for Proximity Graphs (2003)
Ferran Hurtado, Giuseppe Liotta, Henk Meijer
Given a set of n points in the plane, any fi-skeleton and [fl 0 ; fl 1 ]-graph can be computed in quadratic time. The presented algorithms are optimal for fi values that are less than 1 and [fl 0 ;...
Computing Labeled Orthogonal Drawings (2002)
Binucci, Carla, Didimo, Walter, Liotta, Giuseppe, Nonato, Maddalena
This paper studies the problem of computing labeled orthogonal drawings. A label is modeled as a rectangle of prescribed size and it can be associated with either a vertex or an edge. Several...
Orthogonal 3D Shapes of Theta Graphs (2002)
Di Giacomo, Emilio, Liotta, Giuseppe, Patrignani, Maurizio
The recent interest in three dimensional graph drawing has been motivating studies on how to extend two dimensional techniques to higher dimensions. A common approach for computing a 2D orthogonal...
Book Embeddings and Point-Set Embeddings of Series-Parallel Digraphs (2002)
Di Giacomo, Emilio, Didimo, Walter, Liotta, Giuseppe, Wismath, Stephen
An optimal O(n)-time algorithm to compute an upward two-page book embedding of a series-parallel digraph with n vertices is presented. A previous algorithm of Alzohairi and Rival [1] runs in O(n³)...
A Fixed-Parameter Approach to Two-Layer Planarization (2002)
Dujmovic, Vida, Fellows, M., Hallett, M., Kitching, Matthew, Liotta, Giuseppe, McCartin, C., ...
A bipartite graph is biplanar if the vertices can be placed on two parallel lines (layers) in the plane such that there are no edge crossings when edges are drawn straight. The 2-LAYER PLANARIZATION...
Di Giacomo, Emilio, Liotta, Giuseppe
WAVE ( http://lis.ing.unipg.it/wave) is a system for algorithm visualization over the Internet designed with a novel paradigm, called Publication-driven approach [1,2]. The Publication-driven...
Labeling Heuristics for Orthogonal Drawings (2002)
Binucci, Carla, Didimo, Walter, Liotta, Giuseppe, Nonato, Maddalena
This paper studies the problem of computing an orthogonal drawing of a graph with labels along the edges. Labels are not allowed to overlap with each other or with edges to which they are not...
Felsner, Stefan, Liotta, Giuseppe, Wismath, Stephen
This paper investigates the following question: Given an integer grid $\phi$, where $\phi$ is a proper subset of the integer plane or a proper subset of the integer 3d space, which graphs admit...
Computing Labeled Orthogonal Drawings (2002)
Binucci, Carla, Didimo, Walter, Liotta, Giuseppe, Nonato, Maddalena
This paper studies the problem of computing labeled orthogonal drawings. A label is modeled as a rectangle of prescribed size and it can be associated with either a vertex or an edge. Several...
Orthogonal 3D Shapes of Theta Graphs (2002)
Di Giacomo, Emilio, Liotta, Giuseppe, Patrignani, Maurizio
The recent interest in three dimensional graph drawing has been motivating studies on how to extend two dimensional techniques to higher dimensions. A common approach for computing a 2D orthogonal...
Book Embeddings and Point-Set Embeddings of Series-Parallel Digraphs (2002)
Di Giacomo, Emilio, Didimo, Walter, Liotta, Giuseppe, Wismath, Stephen
An optimal O(n)-time algorithm to compute an upward two-page book embedding of a series-parallel digraph with n vertices is presented. A previous algorithm of Alzohairi and Rival [1] runs in O(n³)...
A Fixed-Parameter Approach to Two-Layer Planarization (2002)
Dujmovic, Vida, Fellows, M., Hallett, M., Kitching, Matthew, Liotta, Giuseppe, McCartin, C., ...
A bipartite graph is biplanar if the vertices can be placed on two parallel lines (layers) in the plane such that there are no edge crossings when edges are drawn straight. The 2-LAYER PLANARIZATION...
Di Giacomo, Emilio, Liotta, Giuseppe
WAVE ( http://lis.ing.unipg.it/wave) is a system for algorithm visualization over the Internet designed with a novel paradigm, called Publication-driven approach [1,2]. The Publication-driven...
Labeling Heuristics for Orthogonal Drawings (2002)
Binucci, Carla, Didimo, Walter, Liotta, Giuseppe, Nonato, Maddalena
This paper studies the problem of computing an orthogonal drawing of a graph with labels along the edges. Labels are not allowed to overlap with each other or with edges to which they are not...
Felsner, Stefan, Liotta, Giuseppe, Wismath, Stephen
This paper investigates the following question: Given an integer grid $\phi$, where $\phi$ is a proper subset of the integer plane or a proper subset of the integer 3d space, which graphs admit...
Computing Labeled Orthogonal Drawings (2002)
Binucci, Carla, Didimo, Walter, Liotta, Giuseppe, Nonato, Maddalena
This paper studies the problem of computing labeled orthogonal drawings. A label is modeled as a rectangle of prescribed size and it can be associated with either a vertex or an edge. Several...
Orthogonal 3D Shapes of Theta Graphs (2002)
Di Giacomo, Emilio, Liotta, Giuseppe, Patrignani, Maurizio
The recent interest in three dimensional graph drawing has been motivating studies on how to extend two dimensional techniques to higher dimensions. A common approach for computing a 2D orthogonal...
Book Embeddings and Point-Set Embeddings of Series-Parallel Digraphs (2002)
Di Giacomo, Emilio, Didimo, Walter, Liotta, Giuseppe, Wismath, Stephen
An optimal O(n)-time algorithm to compute an upward two-page book embedding of a series-parallel digraph with n vertices is presented. A previous algorithm of Alzohairi and Rival [1] runs in O(n³)...
A Fixed-Parameter Approach to Two-Layer Planarization (2002)
Dujmovic, Vida, Fellows, M., Hallett, M., Kitching, Matthew, Liotta, Giuseppe, McCartin, C., ...
A bipartite graph is biplanar if the vertices can be placed on two parallel lines (layers) in the plane such that there are no edge crossings when edges are drawn straight. The 2-LAYER PLANARIZATION...
Di Giacomo, Emilio, Liotta, Giuseppe
WAVE ( http://lis.ing.unipg.it/wave) is a system for algorithm visualization over the Internet designed with a novel paradigm, called Publication-driven approach [1,2]. The Publication-driven...
Labeling Heuristics for Orthogonal Drawings (2002)
Binucci, Carla, Didimo, Walter, Liotta, Giuseppe, Nonato, Maddalena
This paper studies the problem of computing an orthogonal drawing of a graph with labels along the edges. Labels are not allowed to overlap with each other or with edges to which they are not...
Felsner, Stefan, Liotta, Giuseppe, Wismath, Stephen
This paper investigates the following question: Given an integer grid $\phi$, where $\phi$ is a proper subset of the integer plane or a proper subset of the integer 3d space, which graphs admit...
On Orthogonal 3D Shapes of Theta Graphs (2002)
Emilio Di Giacomo, Giuseppe Liotta, Maurizio Patrignani
The recent interest in three dimensional graph drawing has been motivating studies on how to extend two dimensional techniques to higher dimensions. A common 2D approach for computing an orthogonal...
Stefan Felsner, Giuseppe Liotta, Stephen Wismath
This paper investigates the following question: Given an integer grid...
Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions (2002)
Stefan Felsner, Giuseppe Liotta, Stephen Wismath
This paper investigates the following question: Given a grid , where is a proper subset of the integer 2D or 3D grid, which graphs admit straight-line crossing-free drawings with vertices located at...
Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions (2002)
Stefan Felsner, Giuseppe Liotta, Stephen Wismath
This paper investigates the following question: Given a grid , where is a proper subset of the integer 2D or 3D grid, which graphs admit straight-line crossing-free drawings with vertices located at...
Orthogonal Drawings of Cycles in 3D Space (Extended Abstract) (2001)
Di Battista, Giuseppe, Liotta, Giuseppe, Lubiw, Anna, Whitesides, Sue
Let C be a directed cycle, whose edges have each been assigned a desired direction in 3D (East, West, North, South, Up, or Down) but no length. We say that C is a shape cycle. We consider the...
Minimum Weight Drawings of Maximal Triangulations (Extended Abstract) (2001)
Lenhart, William, Liotta, Giuseppe
This paper studies the drawability problem for minimum weight triangulations, i.e. whether a triangulation can be drawn so that the resulting drawing is the minimum weight triangulations of the set...
Orthogonal Drawings of Cycles in 3D Space (Extended Abstract) (2001)
Di Battista, Giuseppe, Liotta, Giuseppe, Lubiw, Anna, Whitesides, Sue
Let C be a directed cycle, whose edges have each been assigned a desired direction in 3D (East, West, North, South, Up, or Down) but no length. We say that C is a shape cycle. We consider the...
Minimum Weight Drawings of Maximal Triangulations (Extended Abstract) (2001)
Lenhart, William, Liotta, Giuseppe
This paper studies the drawability problem for minimum weight triangulations, i.e. whether a triangulation can be drawn so that the resulting drawing is the minimum weight triangulations of the set...
Orthogonal Drawings of Cycles in 3D Space (Extended Abstract) (2001)
Di Battista, Giuseppe, Liotta, Giuseppe, Lubiw, Anna, Whitesides, Sue
Let C be a directed cycle, whose edges have each been assigned a desired direction in 3D (East, West, North, South, Up, or Down) but no length. We say that C is a shape cycle. We consider the...
Minimum Weight Drawings of Maximal Triangulations (Extended Abstract) (2001)
Lenhart, William, Liotta, Giuseppe
This paper studies the drawability problem for minimum weight triangulations, i.e. whether a triangulation can be drawn so that the resulting drawing is the minimum weight triangulations of the set...
Turn-Regularity and Planar Orthogonal Drawings (Extended Abstract) (1999)
Bridgeman, Stina, Di Battista, Giuseppe, Didimo, Walter, Liotta, Giuseppe, Tamassia, Roberto, Vismara, Luca
Given an orthogonal representation H with n vertices and bends, we study the problem of computing a planar orthogonal drawing of H with small area. This problem has direct applications to the...
Let G be a degree-3 planar biconnected graph with n vertices. Let Opt(G) be the minimum number of bends in any orthogonal planar drawing of G. We show that G admits a planar orthogonal drawing D with...
Voronoi Drawings of Trees (1999)
Liotta, Giuseppe, Meijer, Henk
This paper investigates the following problem: Given a tree T, can we find a set of points in the plane such that the Voronoi diagram of this set of points is a drawing of T? We study trees that can...
Infinite Trees and the Future (Extended Abstract) (1999)
Demetrescu, Camil, Di Battista, Giuseppe, Finocchi, Irene, Liotta, Giuseppe, Patrignani, Maurizio, Pizzonia, Maurizio
We study the problem of designing layout facilities for the navigation of an "infinite" graph, i. e. a graph that is so large that its visualization is unfeasible, even by gluing together all the...
Turn-Regularity and Planar Orthogonal Drawings (Extended Abstract) (1999)
Bridgeman, Stina, Di Battista, Giuseppe, Didimo, Walter, Liotta, Giuseppe, Tamassia, Roberto, Vismara, Luca
Given an orthogonal representation H with n vertices and bends, we study the problem of computing a planar orthogonal drawing of H with small area. This problem has direct applications to the...
Let G be a degree-3 planar biconnected graph with n vertices. Let Opt(G) be the minimum number of bends in any orthogonal planar drawing of G. We show that G admits a planar orthogonal drawing D with...
Voronoi Drawings of Trees (1999)
Liotta, Giuseppe, Meijer, Henk
This paper investigates the following problem: Given a tree T, can we find a set of points in the plane such that the Voronoi diagram of this set of points is a drawing of T? We study trees that can...
Infinite Trees and the Future (Extended Abstract) (1999)
Demetrescu, Camil, Di Battista, Giuseppe, Finocchi, Irene, Liotta, Giuseppe, Patrignani, Maurizio, Pizzonia, Maurizio
We study the problem of designing layout facilities for the navigation of an "infinite" graph, i. e. a graph that is so large that its visualization is unfeasible, even by gluing together all the...
Turn-Regularity and Planar Orthogonal Drawings (Extended Abstract) (1999)
Bridgeman, Stina, Di Battista, Giuseppe, Didimo, Walter, Liotta, Giuseppe, Tamassia, Roberto, Vismara, Luca
Given an orthogonal representation H with n vertices and bends, we study the problem of computing a planar orthogonal drawing of H with small area. This problem has direct applications to the...
Let G be a degree-3 planar biconnected graph with n vertices. Let Opt(G) be the minimum number of bends in any orthogonal planar drawing of G. We show that G admits a planar orthogonal drawing D with...
Voronoi Drawings of Trees (1999)
Liotta, Giuseppe, Meijer, Henk
This paper investigates the following problem: Given a tree T, can we find a set of points in the plane such that the Voronoi diagram of this set of points is a drawing of T? We study trees that can...
Infinite Trees and the Future (Extended Abstract) (1999)
Demetrescu, Camil, Di Battista, Giuseppe, Finocchi, Irene, Liotta, Giuseppe, Patrignani, Maurizio, Pizzonia, Maurizio
We study the problem of designing layout facilities for the navigation of an "infinite" graph, i. e. a graph that is so large that its visualization is unfeasible, even by gluing together all the...
Infinite Trees and the Future (1999)
Camil Demetrescu, Giuseppe Di Battista, Irene Finocchi, Giuseppe Liotta, Maurizio Patrignani, Maurizio Pizzonia
We study the problem of designing layout facilities for the navigation of an "infinite" graph, i.e. a graph that is so large that its visualization is unfeasible, even by gluing together...
Checking the Convexity of Polytopes and the Planarity of Subdivisions (1998)
Devillers, Olivier, Liotta, Giuseppe, Preparata, Franco P., Tamassia, Roberto
This paper considers the problem of verifying the correctness of geometric structures. In particular, we design simple optimal checkers for convex polytopes in two and higher dimensions, and for...
Drawable and Forbidden Minimum Weight Triangulations (1998)
Lenhart, William, Liotta, Giuseppe
A graph is minimum weight drawable if it admits a straightline drawing that is a minimum weight triangulation of the set of points representing the vertices of the graph. In this paper we consider...
Upward Planarity Checking: "Faces Are More than Polygons" (Extended Abstract) (1998)
Di Battista, Giuseppe, Liotta, Giuseppe
In this paper we look at upward planarity from a new perspective. Namely, we study the problem of checking whether a given drawing is upward planar. Our checker exploits the relationships between...
Drawable and Forbidden Minimum Weight Triangulations (1998)
Lenhart, William, Liotta, Giuseppe
A graph is minimum weight drawable if it admits a straightline drawing that is a minimum weight triangulation of the set of points representing the vertices of the graph. In this paper we consider...
Upward Planarity Checking: "Faces Are More than Polygons" (Extended Abstract) (1998)
Di Battista, Giuseppe, Liotta, Giuseppe
In this paper we look at upward planarity from a new perspective. Namely, we study the problem of checking whether a given drawing is upward planar. Our checker exploits the relationships between...
Checking the Convexity of Polytopes and the Planarity of Subdivisions (1998)
Devillers, Olivier, Liotta, Giuseppe, Preparata, Franco P., Tamassia, Roberto
This paper considers the problem of verifying the correctness of geometric structures. In particular, we design simple optimal checkers for convex polytopes in two and higher dimensions, and for...
Checking the Convexity of Polytopes and the Planarity of Subdivisions (1998)
Devillers, Olivier, Liotta, Giuseppe, Preparata, Franco P., Tamassia, Roberto
This paper considers the problem of verifying the correctness of geometric structures. In particular, we design simple optimal checkers for convex polytopes in two and higher dimensions, and for...
Drawable and Forbidden Minimum Weight Triangulations (1998)
Lenhart, William, Liotta, Giuseppe
A graph is minimum weight drawable if it admits a straightline drawing that is a minimum weight triangulation of the set of points representing the vertices of the graph. In this paper we consider...
Upward Planarity Checking: "Faces Are More than Polygons" (Extended Abstract) (1998)
Di Battista, Giuseppe, Liotta, Giuseppe
In this paper we look at upward planarity from a new perspective. Namely, we study the problem of checking whether a given drawing is upward planar. Our checker exploits the relationships between...
Spirality And Optimal Orthogonal Drawings (1998)
Giuseppe Di Battista, Giuseppe Liotta, Francesco Vargiu
.<F3.8e+05> We deal with the problem of constructing the orthogonal drawing of a graph with the minimum number of bends along the edges. The problem has been recently shown to be NPcomplete in...
Checking the convexity of polytopes and the planarity of subdivisions. (1998)
Devillers, Olivier, Liotta, Giuseppe, Preparata, Franco, Tamassia, Roberto
This paper considers the problem of verifying the correctness of geometric structures. In particular, we design simple optimal checkers for convex polytopes in two and higher dimensions, and for...
Checking the convexity of polytopes and the planarity of subdivisions. (1998)
Devillers, Olivier, Liotta, Giuseppe, Preparata, Franco, Tamassia, Roberto
This paper considers the problem of verifying the correctness of geometric structures. In particular, we design simple optimal checkers for convex polytopes in two and higher dimensions, and for...
Proximity Drawings of Outerplanar Graphs (Preliminary Version). (1997)
Lenhart, William, Liotta, Giuseppe
A proximity drawing of a graph is one in which pairs of adjacent vertices are drawn relatively close together according to some proximity measure while pairs of non-adjacent vertices are drawn...
Low Degree Algorithms for Computing and Checking Gabriel Graphs. (Extended Abstract). (1997)
In the context of robust computational geometry we focus on the problem of computing and checking Gabriel graphs with algorithms that are not affected by degenaracies and have low arithmetic demand....
Proximity Constraints and Representable Trees, (1997)
Bose, Prosenjit, Di Battista, Giuseppe, Lenhart, William, Liotta, Giuseppe
This paper examines an infinite family of proximity drawings of graphs called open and closed B-drawings, first defined by Kirkpatrick and Radke in the context of computational morphology. Such...
Drawing Directed Acyclic Graphs: An Experimantal Study (1997)
Di Battista, Giuseppe, Garg, Ashim, Liotta, Giuseppe, Parise, Armando, Tamassia, Roberto, Tassinari, Emanuele, ...
In this paper we consider the class of directed acyclic graphs (DAGs), and present the results of an experimetal study on four drawing algorithms specifically developed for DAGs. Our study is...
Proximity Drawings of Outerplanar Graphs (extended abstract) (1997)
Lenhart, William, Liotta, Giuseppe
A proximity drawing of a graph is one in which pairs of adjacent vertices are drawn relatively close together according to some proximity measure while pairs of non-adjacent vertices are drawn...
Drawing Directed Acyclic Graphs: An Experimantal Study (1997)
Di Battista, Giuseppe, Garg, Ashim, Liotta, Giuseppe, Parise, Armando, Tamassia, Roberto, Tassinari, Emanuele, ...
In this paper we consider the class of directed acyclic graphs (DAGs), and present the results of an experimetal study on four drawing algorithms specifically developed for DAGs. Our study is...
Proximity Drawings of Outerplanar Graphs (extended abstract) (1997)
Lenhart, William, Liotta, Giuseppe
A proximity drawing of a graph is one in which pairs of adjacent vertices are drawn relatively close together according to some proximity measure while pairs of non-adjacent vertices are drawn...
Drawing Directed Acyclic Graphs: An Experimantal Study (1997)
Di Battista, Giuseppe, Garg, Ashim, Liotta, Giuseppe, Parise, Armando, Tamassia, Roberto, Tassinari, Emanuele, ...
In this paper we consider the class of directed acyclic graphs (DAGs), and present the results of an experimetal study on four drawing algorithms specifically developed for DAGs. Our study is...
Proximity Drawings of Outerplanar Graphs (extended abstract) (1997)
Lenhart, William, Liotta, Giuseppe
A proximity drawing of a graph is one in which pairs of adjacent vertices are drawn relatively close together according to some proximity measure while pairs of non-adjacent vertices are drawn...
Drawing Series-Parallel Graphs on a Box (1997)
Emilio Di Giacomo, Giuseppe Liotta, Stephen K. Wismath
A box is a restricted portion of the three-dimensional integer grid consisting of four parallel lines of in nite length placed one grid unit apart. A box-drawing of a graph is a straight-line...
An Experimental Comparison of Four Graph Drawing Algorithms (1997)
Giuseppe Di Battista, Giuseppe Liotta, Ashim Garg, Roberto Tamassia, Emanuele Tassinari, ...
In this paper we present an extensive experimental study comparing four general-purpose graph drawing algorithms. The four algorithms take as input general graphs (with no restrictions whatsoever on...
GD-Workbench: A System for Prototyping and Testing Graph Drawing Algorithm (1996)
Buti, Luciano, Di Battista, Giuseppe, Liotta, Giuseppe, Tassinari, Emanuele, Vargiu, Francesco, Vismara, Luca
We present a tool for quick prototyping and testing graph drawing algorithms. The user interacts with the system through a diagrammatic interface. Algorithms are visually displayed as directed paths...
The Strength of Weak Proximity (Extended Abstract) (1996)
Di Battista, Giuseppe, Liotta, Giuseppe, Whitesides, Sue
This paper initiates the study of weak proximity drawings of graphs and demonstrates their advantages over strong proximity drawings in certain cases. Weak proximity drawings are straight line...
How to Draw Outerplanar Minimum Weight Triangulations (1996)
Lenhart, William, Liotta, Giuseppe
In this paper we consider the problem of characterizing those graphs that can be drawn as minimum weight triangulations and answer the question for maximal outerplanar graphs. We provide a complete...
GD-Workbench: A System for Prototyping and Testing Graph Drawing Algorithm (1996)
Buti, Luciano, Di Battista, Giuseppe, Liotta, Giuseppe, Tassinari, Emanuele, Vargiu, Francesco, Vismara, Luca
We present a tool for quick prototyping and testing graph drawing algorithms. The user interacts with the system through a diagrammatic interface. Algorithms are visually displayed as directed paths...
The Strength of Weak Proximity (Extended Abstract) (1996)
Di Battista, Giuseppe, Liotta, Giuseppe, Whitesides, Sue
This paper initiates the study of weak proximity drawings of graphs and demonstrates their advantages over strong proximity drawings in certain cases. Weak proximity drawings are straight line...
How to Draw Outerplanar Minimum Weight Triangulations (1996)
Lenhart, William, Liotta, Giuseppe
In this paper we consider the problem of characterizing those graphs that can be drawn as minimum weight triangulations and answer the question for maximal outerplanar graphs. We provide a complete...
GD-Workbench: A System for Prototyping and Testing Graph Drawing Algorithm (1996)
Buti, Luciano, Di Battista, Giuseppe, Liotta, Giuseppe, Tassinari, Emanuele, Vargiu, Francesco, Vismara, Luca
We present a tool for quick prototyping and testing graph drawing algorithms. The user interacts with the system through a diagrammatic interface. Algorithms are visually displayed as directed paths...
The Strength of Weak Proximity (Extended Abstract) (1996)
Di Battista, Giuseppe, Liotta, Giuseppe, Whitesides, Sue
This paper initiates the study of weak proximity drawings of graphs and demonstrates their advantages over strong proximity drawings in certain cases. Weak proximity drawings are straight line...
How to Draw Outerplanar Minimum Weight Triangulations (1996)
Lenhart, William, Liotta, Giuseppe
In this paper we consider the problem of characterizing those graphs that can be drawn as minimum weight triangulations and answer the question for maximal outerplanar graphs. We provide a complete...
Proximity Drawings of Outerplanar Graphs (1996)
William Lenhart, Giuseppe Liotta, William Lenhart
A proximity drawing of a graph is one in which pairs of adjacent vertices are drawn relatively close together according to some proximity measure while pairs of non-adjacent vertices are drawn...
Low Degree Algorithms for Computing and Checking Gabriel Graphs (1996)
) Giuseppe Liotta Center for Geometric Computing Department of Computer Science, Brown University 115 Waterman Street, Providence, RI 02912--1910, USA gl@cs.brown.edu Abstract In the context of...
The Strength of Weak Proximity (1996)
Giuseppe Di Battista, Giuseppe Liotta, Sue H. Whitesides
This paper initiates the study of weak proximity drawings of graphs and demonstrates their advantages over strong proximity drawings in certain cases. Weak proximity drawings are straight line...
Proximity Constraints and Representable Trees (1996)
Prosenjit Bose, Giuseppe Di Battista, William Lenhart, Giuseppe Liotta, Roma Italy
This paper examines an infinite family of proximity drawings of graphs called open and closed fi-drawings, first defined by Kirkpatrick and Radke [15, 21] in the context of computational morphology....
Robust Proximity Queries in Implicit Voronoi Diagrams (1996)
Giuseppe Liotta, F. P. Preparata, Roberto Tamassia, Franco P. Preparata, Roberto Tamassia
In the context of methodologies intended to confer robustness to geometric algorithms, we elaborate on the exact computation paradigm and formalize the notion of degree of a geometric algorithm, as a...
Algorithm Animation Over the World Wide Web (1996)
James Baker, Isabel F. Cruz, Giuseppe Liotta, Roberto Tamassia
In this paper we propose a new model, called Mocha, for providing algorithm animation over the World Wide Web. Mocha is a distributed model with a client-server architecture that optimally partitions...
A New Model for Algorithm Animation Over the WWW (1996)
James E. Baker, Isabel F. Cruz, Giuseppe Liotta, Roberto Tamassia
Introduction Algorithm animation helps the end user to understand algorithms by following visually their stepby -step execution, a complex task if relying on the textual program alone. There is a...
Drawing Outerplanar Minimum Weight Triangulations (short abstract) (1996)
William Lenhart, Giuseppe Liotta
this paper we examine the problem of characterizing those triangulations admitting a minimum weight drawing and answer the question for maximal outerplanar graphs. The contribution is twofold: 1....
Proximity Drawability: A Survey (extended abstract) (1995)
Di Battista, Giuseppe, Lenhart, William, Liotta, Giuseppe
Increasing attention has been given recently to drawings of graphs in which edges connect vertices based on some notion of proximity. Among such drawings are Gabriel, relative neighborhood, Delaunay,...
Proximity Constraints and Representable Trees (extended abstract) (1995)
Bose, Prosenjit, Di Battista, Giuseppe, Lenhart, William, Liotta, Giuseppe
A family of proximity drawings of graphs called open and closed \beta-drawings, first defined in [15], and including the Gabriel, relative neighborhood and strip drawings, are investigated. Complete...
Recognizing Rectangle of Influence Drawable Graphs (extended abstract) (1995)
ElGindy, H., Liotta, Giuseppe, Lubiw, Anna, Meijer, Henk, Whitesides, Sue
Given two points x and y in the plane the rectangle of influence of x and y is the axis-aligned rectangle having x and y at opposite corners. The rectangle of influence drawing of a graph G is a...
Proximity Drawability: A Survey (extended abstract) (1995)
Di Battista, Giuseppe, Lenhart, William, Liotta, Giuseppe
Increasing attention has been given recently to drawings of graphs in which edges connect vertices based on some notion of proximity. Among such drawings are Gabriel, relative neighborhood, Delaunay,...
Proximity Constraints and Representable Trees (extended abstract) (1995)
Bose, Prosenjit, Di Battista, Giuseppe, Lenhart, William, Liotta, Giuseppe
A family of proximity drawings of graphs called open and closed \beta-drawings, first defined in [15], and including the Gabriel, relative neighborhood and strip drawings, are investigated. Complete...
Recognizing Rectangle of Influence Drawable Graphs (extended abstract) (1995)
ElGindy, H., Liotta, Giuseppe, Lubiw, Anna, Meijer, Henk, Whitesides, Sue
Given two points x and y in the plane the rectangle of influence of x and y is the axis-aligned rectangle having x and y at opposite corners. The rectangle of influence drawing of a graph G is a...
Proximity Drawability: A Survey (extended abstract) (1995)
Di Battista, Giuseppe, Lenhart, William, Liotta, Giuseppe
Increasing attention has been given recently to drawings of graphs in which edges connect vertices based on some notion of proximity. Among such drawings are Gabriel, relative neighborhood, Delaunay,...
Proximity Constraints and Representable Trees (extended abstract) (1995)
Bose, Prosenjit, Di Battista, Giuseppe, Lenhart, William, Liotta, Giuseppe
A family of proximity drawings of graphs called open and closed \beta-drawings, first defined in [15], and including the Gabriel, relative neighborhood and strip drawings, are investigated. Complete...
Recognizing Rectangle of Influence Drawable Graphs (extended abstract) (1995)
ElGindy, H., Liotta, Giuseppe, Lubiw, Anna, Meijer, Henk, Whitesides, Sue
Given two points x and y in the plane the rectangle of influence of x and y is the axis-aligned rectangle having x and y at opposite corners. The rectangle of influence drawing of a graph G is a...
An Experimental Comparison of Three Graph Drawing Algorithms (Extended Abstract) (1995)
Giuseppe Di Battista, Ashim Garg, Giuseppe Liotta, Roberto Tamassia, Emanuele Tassinari, Francesco Vargiu
In this paper we present an extensive experimental study...
Robust Proximity Queries: an Illustration of Degree-driven Algorithm Design
Giuseppe Liotta, Franco P. Preparata, Roberto Tamassia
In the context of methodologies intended to confer robustness to geometric algorithms, we elaborate on the exact computation paradigm and formalize the notion of degree of a geometric algorithm, as a...