10 results on '"LIOTTA, GIUSEPPE"'
Search Results
2. Voronoi drawings of trees
- Author
-
Liotta, Giuseppe and Meijer, Henk
- Subjects
- *
VORONOI polygons , *GEOMETRIC group theory - Abstract
We study the problem of characterizing sets of points whose Voronoi diagrams are trees and if so, what are the combinatorial properties of these trees. The second part of the problem can be naturally turned into the following graph drawing question: Given a tree
T , can one representT so that the resulting drawing is a Voronoi diagram of some set of points? We investigate the problem both in the Euclidean and in the Manhattan metric. The major contributions of this paper are as follows. [Copyright &y& Elsevier]- We characterize those trees that can be drawn as Voronoi diagrams in the Euclidean metric.
- We characterize those sets of points whose Voronoi diagrams are trees in the Manhattan metric.
- We show that the maximum vertex degree of any tree that can be drawn as a Manhattan Voronoi diagram is at most five and prove that this bound is tight.
- We characterize those binary trees that can be drawn as Manhattan Voronoi diagrams.
- Published
- 2003
- Full Text
- View/download PDF
3. 1-bend upward planar slope number of SP-digraphs.
- Author
-
Di Giacomo, Emilio, Liotta, Giuseppe, and Montecchiani, Fabrizio
- Subjects
- *
DRAWING , *ALGORITHMS , *EDGES (Geometry) , *CONSTRUCTION - Abstract
It is proved that every series-parallel digraph whose maximum vertex degree is Δ admits an upward planar drawing with at most one bend per edge such that each edge segment has one of Δ distinct slopes. The construction is worst-case optimal in terms of the number of slopes, and it gives rise to drawings with optimal angular resolution π Δ. A variant of the drawing algorithm is used to show that (non-directed) reduced series-parallel graphs and flat series-parallel graphs have a (non-upward) 1-bend planar drawing with ⌈ Δ 2 ⌉ distinct slopes if biconnected, and with ⌈ Δ 2 ⌉ + 1 distinct slopes if connected. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
4. Matched drawability of graph pairs and of graph triples
- Author
-
Grilli, Luca, Hong, Seok-Hee, Liotta, Giuseppe, Meijer, Henk, and Wismath, Stephen K.
- Subjects
- *
COMBINATORIAL geometry , *GRAPH theory , *ALGORITHMS , *EMBEDDINGS (Mathematics) , *MATHEMATICAL analysis , *GEOMETRIC analysis - Abstract
Abstract: The contribution of this paper is twofold. It presents a new approach to the matched drawability problem of pairs of planar graphs and it provides four algorithms based on this approach for drawing the pairs , , and . Further, it initiates the study of the matched drawability of triples of planar graphs: it presents an algorithm to compute a matched drawing of a triple of cycles and an algorithm to compute a matched drawing of a caterpillar and two unlabeled level planar graphs. The results extend previous work on the subject and relate to existing literature about simultaneous embeddability and unlabeled level planarity. [Copyright &y& Elsevier]
- Published
- 2010
- Full Text
- View/download PDF
5. Orthogonal drawings of graphs with vertex and edge labels
- Author
-
Binucci, Carla, Didimo, Walter, Liotta, Giuseppe, and Nonato, Maddalena
- Subjects
- *
GRAPHIC methods , *ALGORITHMS , *INFORMATION resources , *EUCLID'S elements - Abstract
Abstract: This paper studies the problem of computing orthogonal drawings of graphs with labels on vertices and edges. Our research is mainly motivated by Software Engineering and Information Systems domains, where tools like UML diagrams and ER-diagrams are considered fundamental for the design of sophisticated systems and/or complex data bases collecting enormous amount of information. A label is modeled as a rectangle of prescribed width and height and it can be associated with either a vertex or an edge. Our drawing algorithms guarantee no overlaps between labels, vertices, and edges and take advantage of the information about the set of labels to compute the geometry of the drawing. Several additional optimization goals are taken into account. Namely, the labeled drawing can be required to have either minimum total edge length, or minimum width, or minimum height, or minimum area among those preserving a given orthogonal representation. All these goals lead to NP-hard problems. We present MILP models to compute optimal drawings with respect to the first three goals and an exact algorithm that is based on these models to compute a labeled drawing of minimum area. We also present several heuristics for computing compact labeled orthogonal drawings and experimentally validate their performances, comparing their solutions against the optimum. [Copyright &y& Elsevier]
- Published
- 2005
- Full Text
- View/download PDF
6. Curve-constrained drawings of planar graphs
- Author
-
Di Giacomo, Emilio, Didimo, Walter, Liotta, Giuseppe, and Wismath, Stephen K.
- Subjects
- *
CURVES , *GRAPHIC methods , *CONCAVE functions , *REAL variables - Abstract
Let
C be the family of 2D curves described by concave functions, letG be a planar graph, and letL be a linear ordering of the vertices ofG .L is a curve embedding ofG if for any given curveΛ∈C there exists a planar drawing ofG such that: (i) the vertices are constrained to be onΛ with the same ordering as inL , and (ii) the edges are polylines with at most one bend. Informally speaking, a curve embedding can be regarded as a two-page book embedding in which the spine is bent. Although deciding whether a graph has a two-page book embedding is an NP-hard problem, in this paper it is proven that every planar graph has a curve embedding which can be computed in linear time. Applications of the concept of curve embedding to upward drawability and point-set embeddability problems are also presented. [Copyright &y& Elsevier]- Published
- 2005
- Full Text
- View/download PDF
7. Visibility representations of boxes in 2.5 dimensions.
- Author
-
Arleo, Alessio, Binucci, Carla, Di Giacomo, Emilio, Evans, William S., Grilli, Luca, Liotta, Giuseppe, Meijer, Henk, Montecchiani, Fabrizio, Whitesides, Sue, and Wismath, Stephen
- Subjects
- *
REPRESENTATION theory , *DIMENSIONS , *GRAPH theory , *MATHEMATICAL mappings , *GEOMETRY - Abstract
Visibility representations are a well-known paradigm to represent graphs. From a high-level perspective, a visibility representation of a graph G maps the vertices of G to non-overlapping geometric objects and the edges of G to visibilities, i.e., segments that do not intersect any geometric object other than at their end-points. In this paper, we initiate the study of 2.5D box visibility representations (2.5D-BRs) where vertices are mapped to 3D boxes having the bottom face in the plane z = 0 and edges are unobstructed lines of sight parallel to the x - or y -axis. We prove that: ( i ) Every complete bipartite graph admits a 2.5D-BR; ( i i ) The complete graph K n admits a 2.5D-BR if and only if n ⩽ 19 ; ( i i i ) Every graph with pathwidth at most 7 admits a 2.5D-BR, which can be computed in linear time. We then turn our attention to 2.5D grid box representations (2.5D-GBRs), which are 2.5D-BRs such that the bottom face of every box is a unit square at integer coordinates. We show that an n -vertex graph that admits a 2.5D-GBR has at most 4 n − 6 n edges and this bound is tight. Finally, we prove that deciding whether a given graph G admits a 2.5D-GBR with a given footprint is NP-complete (the footprint of a 2.5D-BR Γ is the set of bottom faces of the boxes in Γ). [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
8. Approximate proximity drawings
- Author
-
Evans, William, Gansner, Emden, Kaufmann, Michael, Liotta, Giuseppe, Meijer, Henk, and Spillner, Andreas
- Subjects
- *
APPROXIMATION theory , *PROXIMITY spaces , *GRAPH theory , *REAL numbers , *MATHEMATICAL analysis , *MULTIPLICATION - Abstract
Abstract: We introduce and study a generalization of the well-known region of influence proximity drawings, called -proximity drawings. Intuitively, given a definition of proximity and two real numbers and , an -proximity drawing of a graph is a planar straight-line drawing Γ such that: (i) for every pair of adjacent vertices u, v, their proximity region “shrunk” by the multiplicative factor does not contain any vertices of Γ; (ii) for every pair of non-adjacent vertices u, v, their proximity region “expanded” by the factor contains some vertices of Γ other than u and v. In particular, the locations of the vertices in such a drawing do not always completely determine which edges must be present/absent, giving us some freedom of choice. We show that this generalization significantly enlarges the family of representable planar graphs for relevant definitions of proximity drawings, including Gabriel drawings, Delaunay drawings, and β-drawings, even for arbitrarily small values of and . We also study the extremal case of -proximity drawings, which generalize the well-known weak proximity drawing paradigm. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
9. Upward straight-line embeddings of directed graphs into point sets
- Author
-
Binucci, Carla, Di Giacomo, Emilio, Didimo, Walter, Estrella-Balderrama, Alejandro, Frati, Fabrizio, Kobourov, Stephen G., and Liotta, Giuseppe
- Subjects
- *
EMBEDDINGS (Mathematics) , *DIRECTED graphs , *POINT set theory , *ACYCLIC model , *MATHEMATICAL mappings , *CONVEX geometry - Abstract
Abstract: In this paper we study the problem of computing an upward straight-line embedding of a planar DAG (directed acyclic graph) G into a point set S, i.e. a planar drawing of G such that each vertex is mapped to a point of S, each edge is drawn as a straight-line segment, and all the edges are oriented according to a common direction. In particular, we show that no biconnected DAG admits an upward straight-line embedding into every point set in convex position. We provide a characterization of the family of DAGs that admit an upward straight-line embedding into every convex point set such that the points with the largest and the smallest y-coordinate are consecutive in the convex hull of the point set. We characterize the family of DAGs that contain a Hamiltonian directed path and that admit an upward straight-line embedding into every point set in general position. We also prove that a DAG whose underlying graph is a tree does not always have an upward straight-line embedding into a point set in convex position and we describe how to construct such an embedding for a DAG whose underlying graph is a path. Finally, we give results about the embeddability of some sub-classes of DAGs whose underlying graphs are trees on point set in convex and in general position. [Copyright &y& Elsevier]
- Published
- 2010
- Full Text
- View/download PDF
10. Colored anchored visibility representations in 2D and 3D space.
- Author
-
Binucci, Carla, Di Giacomo, Emilio, Hong, Seok-Hee, Liotta, Giuseppe, Meijer, Henk, Sacristán, Vera, and Wismath, Stephen
- Subjects
- *
VISIBILITY , *REPRESENTATIONS of graphs , *GEOMETRIC vertices , *SPACE - Abstract
In a visibility representation of a graph G , the vertices are represented by non-overlapping geometric objects, while the edges are represented as segments that only intersect the geometric objects associated with their end-vertices. Given a set P of n points, an Anchored Visibility Representation of a graph G with n vertices is a visibility representation such that for each vertex v of G , the geometric object representing v contains a point of P. We prove positive and negative results about the existence of anchored visibility representations under various models, both in 2D and in 3D space. We consider the case when the mapping between the vertices and the points is not given and the case when it is only partially given. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.