17 results on '"Liotta, Giuseppe"'
Search Results
2. Simultaneous visibility representations of plane st-graphs using L-shapes.
- Author
-
Evans, William S., Liotta, Giuseppe, and Montecchiani, Fabrizio
- Subjects
- *
GRAPH theory , *SET theory , *HORIZONTAL integration , *ROTATIONAL motion , *QUADRATIC forms - Abstract
Let 〈 G r , G b 〉 be a pair of plane st -graphs with the same vertex set V . A simultaneous visibility representation with L-shapes of 〈 G r , G b 〉 is a pair of bar visibility representations 〈 Γ r , Γ b 〉 such that, for every vertex v ∈ V , Γ r ( v ) and Γ b ( v ) are a horizontal and a vertical segment, respectively, which share an end-point. In other words, every vertex is drawn as an L-shape, every edge of G r is a vertical visibility segment, and every edge of G b is a horizontal visibility segment. Also, no two L-shapes intersect each other. An L-shape has four possible rotations, and we assume that each vertex is given a rotation for its L-shape as part of the input. Our main results are: (i) a characterization of those pairs of plane st -graphs admitting such a representation, (ii) a quadratic time algorithm to recognize them, and (iii) a linear time drawing algorithm if the test is positive. As an application, starting from a simultaneous visibility representation with L-shapes, we show how to compute a simultaneous embedding of the two graphs with at most two bends per edge and right-angle crossings. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
3. Right angle crossing graphs and 1-planarity
- Author
-
Eades, Peter and Liotta, Giuseppe
- Subjects
- *
PLANAR graphs , *GRAPH theory , *COMBINATORICS , *INTERSECTION theory , *PROOF theory , *ALGEBRAIC geometry - Abstract
Abstract: A Right Angle Crossing Graph (also called a RAC graph for short) is a graph that has a straight-line drawing where any two crossing edges are orthogonal to each other. A -planar graph is a graph that has a drawing where every edge is crossed at most once. This paper studies the combinatorial relationship between the family of RAC graphs and the family of -planar graphs. It is proved that: (1) all RAC graphs having maximal edge density belong to the intersection of the two families; and (2) there is no inclusion relationship between the two families. As a by-product of the proof technique, it is also shown that every RAC graph with maximal edge density is the union of two maximal planar graphs. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
4. Volume requirements of 3D upward drawings
- Author
-
Di Giacomo, Emilio, Liotta, Giuseppe, Meijer, Henk, and Wismath, Stephen K.
- Subjects
- *
HASSE diagrams , *DIRECTED graphs , *MATHEMATICAL analysis , *TREE graphs , *CHARTS, diagrams, etc. , *GRAPH theory , *DIMENSIONS - Abstract
Abstract: This paper studies the problem of drawing directed acyclic graphs in three dimensions in the straight-line grid model so that all directed edges are oriented in a common (upward) direction. We show that there exists a family of outerplanar directed acyclic graphs whose volume requirement is super-linear. We also prove that for the case of directed trees a linear-volume upper bound is achievable. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
5. Parametric Graph Drawing.
- Author
-
Bertolazzi, Paola, Di Battista, Giuseppe, and Liotta, Giuseppe
- Subjects
GRAPH theory ,ALGORITHMS ,AUTOMATION ,SOFTWARE engineering ,PROGRAMMING languages ,ELECTRONIC data processing - Abstract
A diagram is a drawing on the plane that represents a graph-like structure, where nodes are represented by symbols and edges are represented by curves connecting pairs of symbols. An automatic layout facility is a tool that receives as input a graph-like structure and is able to produce a diagram that nicely represents such a structure. Many systems use diagrams in the interaction with the users; thus, automatic layout facilities and algorithms for graphs layout have been extensively studied in the last years. We present a new approach in designing an automatic layout facility. Our approach is based on a modular management of a large collection of algorithms and on a strategy that, given the requirements of an application, selects a suitable algorithm for such requirements. The proposed approach has been used for designing the automatic layout facility of Diagram Server, a network server that offers to its clients several facilities for managing diagrams. [ABSTRACT FROM AUTHOR]
- Published
- 1995
- Full Text
- View/download PDF
6. On RAC drawings of 1-planar graphs.
- Author
-
Bekos, Michael A., Didimo, Walter, Liotta, Giuseppe, Mehrabi, Saeed, and Montecchiani, Fabrizio
- Subjects
- *
GRAPH theory , *RIGHT angle , *PATHS & cycles in graph theory , *PLANAR graphs , *LITERATURE reviews - Abstract
A drawing of a graph is 1-planar if each edge is crossed at most once. A graph is 1-planar if it has a 1-planar drawing. A k-bend RAC (Right Angle Crossing) drawing of a graph is a polyline drawing where each edge has at most k bends and edges cross only at right angles. A graph is k-bend RAC if it has a k -bend RAC drawing. A 0-bend RAC graph (drawing) is also called a straight-line RAC graph (drawing) . The relationships between 1-planar and k -bend RAC graphs have been partially studied in the literature. It is known that there are both 1-planar graphs that are not straight-line RAC and straight-line RAC graphs that are not 1-planar. The existence of 1-planar straight-line RAC drawings has been proven only for restricted families of 1-planar graphs. Two of the main questions still open are: ( i ) What is the complexity of deciding whether a graph has a drawing that is both 1-planar and straight-line RAC? ( i i ) Does every 1-planar graph have a drawing that is both 1-planar and 1-bend RAC? In this paper we answer these two questions. Namely, we prove an NP-hardness result for the first question, and we positively answer the second question by describing a drawing algorithm for 1-planar graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
7. Large graph visualizations using a distributed computing platform.
- Author
-
Arleo, Alessio, Didimo, Walter, Liotta, Giuseppe, and Montecchiani, Fabrizio
- Subjects
- *
DATA visualization , *GRAPH theory , *DISTRIBUTED computing , *BIG data , *CLOUD computing - Abstract
Big Data analytics is recognized as one of the major issues in our current information society, and raises several challenges and opportunities in many fields, including economy and finance, e-commerce, public health and administration, national security, and scientific research. The use of visualization techniques to make sense of large volumes of information is an essential ingredient, especially for the analysis of complex interrelated data, which are represented as graphs. The growing availability of powerful and inexpensive cloud computing services naturally motivates the study of distributed graph visualization algorithms, able to scale to the size of large graphs. We study the problem of designing a distributed visualization algorithm that must be simple to implement and whose computing infrastructure does not require major hardware or software investments. We design, implement, and experiment a force-directed algorithm in Giraph, a popular open source framework for distributed computing, based on a vertex-centric design paradigm. The algorithm is tested both on real and artificial graphs with up to one million edges. The experiments show the scalability and effectiveness of our technique when compared to a centralized implementation of the same force-directed model. Graphs with about one million edges can be drawn in a few minutes, by spending about 1 USD per drawing with a cloud computing infrastructure of Amazon. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
8. Area requirement of graph drawings with few crossings per edge.
- Author
-
Di Giacomo, Emilio, Didimo, Walter, Liotta, Giuseppe, and Montecchiani, Fabrizio
- Subjects
- *
GRAPH theory , *PLANAR graphs , *NUMBER theory , *MATHEMATICAL proofs , *ALGORITHMS , *MATHEMATICAL bounds - Abstract
Abstract: In this paper we study how to compute compact straight-line drawings of planar graphs with a limited number of crossings per edge. We prove that every outerplanar graph can be drawn in area using a sub-linear number of crossings per edge, and that for any given number , every outerplanar graph admits an area drawing with crossing per edge. The drawing algorithms run in linear time and can be also generalized to another meaningful sub-family of series–parallel graphs with bounded vertex-degree. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
9. Drawing graphs with right angle crossings
- Author
-
Didimo, Walter, Eades, Peter, and Liotta, Giuseppe
- Subjects
- *
GRAPHIC methods , *GRAPH theory , *COMBINATORICS , *ALGORITHMS , *VISUALIZATION , *COGNITION - Abstract
Abstract: Cognitive experiments show that humans can read graph drawings in which all edge crossings are at right angles equally well as they can read planar drawings; they also show that the readability of a drawing is heavily affected by the number of bends along the edges. A graph visualization whose edges can only cross perpendicularly is called a RAC (Right Angle Crossing) drawing. This paper initiates the study of combinatorial and algorithmic questions related to the problem of computing RAC drawings with few bends per edge. Namely, we study the interplay between number of bends per edge and total number of edges in RAC drawings. We establish upper and lower bounds on these quantities by considering two classical graph drawing scenarios: The one where the algorithm can choose the combinatorial embedding of the input graph and the one where this embedding is fixed. [Copyright &y& Elsevier]
- Published
- 2011
- Full Text
- View/download PDF
10. 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
11. Point-set embeddings of trees with given partial drawings
- Author
-
Di Giacomo, Emilio, Didimo, Walter, Liotta, Giuseppe, Meijer, Henk, and Wismath, Stephen K.
- Subjects
- *
EMBEDDINGS (Mathematics) , *TREE graphs , *GRAPH theory , *SET theory , *PLANE geometry , *MATHEMATICAL mappings , *LINE geometry - Abstract
Abstract: 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 S. A geometric point-set embedding is a point-set embedding with no edge bends. This paper studies the following problem: The input is a set S of n points, a planar graph G with n vertices, and a geometric point-set embedding of a subgraph on a subset of S. The desired output is a point-set embedding of G on S that includes the given partial drawing of . We concentrate on trees and show how to compute the output in time in a real-RAM model and with at most edges with at most bends, where k is the number of vertices of the given subdrawing. We also prove that there are instances of the problem which require at least bends on edges. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
12. -Spine, 1-bend planarity
- Author
-
Giacomo, Emilio Di, Didimo, Walter, Liotta, Giuseppe, and Suderman, Matthew
- Subjects
- *
GRAPH theory , *MATHEMATICS , *NUMERICAL analysis , *MATHEMATICAL analysis - Abstract
Abstract: In this paper, we study k-spine, h-bend planar drawings in which each vertex of a planar graph G lies on one of horizontal lines and each edge of G is drawn as a polyline containing at most bends. A graph with a k-spine, h-bend planar drawing is said to be k-spine, h-bend planar. We mainly focus on k-spine, 1-bend planar drawings, showing that for each , there exists a planar graph that is not k-spine, 1-bend planar, and furthermore, that it is -hard to test k-spine, 1-bend planarity. Given this complexity result, we further narrow our focus onto 2-spine, 1-bend planar drawings. We characterize 2-spine, 1-bend planarity using a new generalization of Hamiltonian graphs that we call Hamiltonian-with-handles graphs. We observe that our characterization naturally extends the connection between 2-page book embeddings and Hamiltonicity. Finally, we use our characterization to show that 2-outerplanar graphs are 2-spine, 1-bend planar. [Copyright &y& Elsevier]
- Published
- 2006
- Full Text
- View/download PDF
13. 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
14. [formula omitted]-page and [formula omitted]-page drawings with bounded number of crossings per edge.
- Author
-
Binucci, Carla, Giacomo, Emilio Di, Hossain, Md. Iqbal, and Liotta, Giuseppe
- Subjects
- *
GRAPH theory , *MATHEMATICAL bounds , *NUMBER theory , *PATHS & cycles in graph theory , *PLANAR graphs - Abstract
A drawing of a graph such that the vertices are drawn as points along a line and each edge is a circular arc in one of the two half-planes defined by this line is called a 2 -page drawing. If all edges are in the same half-plane, the drawing is called a 1 -page drawing. We want to compute 1 -page and 2 -page drawings of planar graphs such that the number of crossings per edge does not depend on the number of vertices. We show that for any constant k , there exist planar graphs that require more than k crossings per edge in both 1 -page and 2 -page drawings. We then prove that if the vertex degree is bounded by Δ , every planar 3-tree has a 2 -page drawing with a number of crossings per edge that only depends on Δ . Finally, we show a similar result for 1 -page drawings of partial 2 -trees. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
15. A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system.
- Author
-
Eades, Peter, Hong, Seok-Hee, Katoh, Naoki, Liotta, Giuseppe, Schweitzer, Pascal, and Suzuki, Yusuke
- Subjects
- *
LINEAR systems , *COMPUTER algorithms , *GRAPH theory , *EMBEDDED computer systems , *PLANAR graphs , *PROBLEM solving - Abstract
Abstract: A 1-planar graph is a graph that can be embedded in the plane with at most one crossing per edge. It is known that testing 1-planarity of a graph is NP-complete. In this paper, we consider maximal 1-planar graphs. A graph G is maximal 1-planar if addition of any edge destroys 1-planarity of G. We first study combinatorial properties of maximal 1-planar embeddings. In particular, we show that in a maximal 1-planar embedding, the graph induced by the non-crossing edges is spanning and biconnected. Using the properties, we show that the problem of testing maximal 1-planarity of a graph G can be solved in linear time, if a rotation system Φ (i.e., the circular ordering of edges for each vertex) is given. We also prove that there is at most one maximal 1-planar embedding ξ of G that is consistent with the given rotation system Φ. Our algorithm also produces such an embedding in linear time, if it exists. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
16. 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
17. Bounds on the crossing resolution of complete geometric graphs
- Author
-
Di Giacomo, Emilio, Didimo, Walter, Eades, Peter, Hong, Seok-Hee, and Liotta, Giuseppe
- Subjects
- *
SET theory , *GEOMETRIC analysis , *GRAPH theory , *MAXIMA & minima , *ANGLES , *MATHEMATICS - Abstract
Abstract: The crossing resolution of a geometric graph is the minimum crossing angle at which any two edges cross each other. In this paper, we present upper and lower bounds to the crossing resolution of the complete geometric graphs. [Copyright &y& Elsevier]
- Published
- 2012
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.