11 results on '"Di Battista, Giuseppe"'
Search Results
2. Upward Planar Morphs.
- Author
-
Da Lozzo, Giordano, Di Battista, Giuseppe, Frati, Fabrizio, Patrignani, Maurizio, and Roselli, Vincenzo
- Subjects
- *
PLANAR graphs , *DIRECTED graphs , *DRAWING - Abstract
We prove that, given two topologically-equivalent upward planar straight-line drawings of an n-vertex directed graph G, there always exists a morph between them such that all the intermediate drawings of the morph are upward planar and straight-line. Such a morph consists of O(1) morphing steps if G is a reduced planar st-graph, O(n) morphing steps if G is a planar st-graph, O(n) morphing steps if G is a reduced upward planar graph, and O (n 2) morphing steps if G is a general upward planar graph. Further, we show that Ω (n) morphing steps might be necessary for an upward planar morph between two topologically-equivalent upward planar straight-line drawings of an n-vertex path. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
3. Windrose Planarity: Embedding Graphs with Direction-Constrained Edges.
- Author
-
ANGELINI, PATRIZIO, DA LOZZO, GIORDANO, DI BATTISTA, GIUSEPPE, DI DONATO, VALENTINO, KINDERMANN, PHILIPP, ROTE, GÜNTER, and RUTTER, IGNAZ
- Subjects
PLANAR graphs ,ALGORITHMS ,NP-hard problems ,EDGES (Geometry) - Abstract
Given a planar graph G and a partition of the neighbors of each vertex v in four sets v↗, v↖, v↙, and v↘, the problem Windrose Planarity asks to decide whether G admits a windrose-planar drawing, that is, a planar drawing in which (i) each neighbor u ∈ v↗v is above and to the right of v, (ii) each neighbor u ∈ v↖ is above and to the left of v, (iii) each neighbor u ∈ v↙ is below and to the left of v, (iv) each neighbor u ∈ v↘ is below and to the right of v, and (v) edges are represented by curves that are monotone with respect to each axis. By exploiting both the horizontal and the vertical relationship among vertices, windrose-planar drawings allow us to simultaneously visualize two partial orders defined by means of the edges of the graph. Although the problem is NP-hard in the general case, we give a polynomial-time algorithm for testing whether there exists a windrose-planar drawing that respects a given combinatorial embedding. This algorithm is based on a characterization of the plane triangulations admitting a windrose-planar drawing. Furthermore, for any embedded graph with n vertices that has a windrose-planar drawing, we can construct one with at most one bend per edge and with at most 2n-5 bends in total, which lies on the 3n × 3n grid. The latter result contrasts with the fact that straight-line windrose-planar drawings may require exponential area. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
4. Strip Planarity Testing for Embedded Planar Graphs.
- Author
-
Angelini, Patrizio, Da Lozzo, Giordano, Di Battista, Giuseppe, and Frati, Fabrizio
- Subjects
PLANAR graphs ,POLYNOMIAL time algorithms ,COMBINATORICS ,COMPUTER workstation clusters ,COMPUTER algorithms - Published
- 2017
- Full Text
- View/download PDF
5. ON THE QUEUE NUMBER OF PLANAR GRAPHS.
- Author
-
DI BATTISTA, GIUSEPPE, FRATI, FABRIZIO, and PACH, JÁNOS
- Subjects
- *
PLANAR graphs , *QUEUING theory , *GRAPH theory , *GEOMETRY , *MATHEMATICAL research - Abstract
We prove that planar graphs have O(log² n) queue number, thus improving upon the previous O(√n) upper bound. Consequently, planar graphs admit three-dimensional straight-line crossing-free grid drawings in O(n log8 n) volume, thus improving upon the previous O(n3/2) upper bound. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
6. NONCONVEX REPRESENTATIONS OF PLANE GRAPHS.
- Author
-
DI BATTISTA, GIUSEPPE, FRATI, FABRIZIO, and PATRIGNANI, MAURIZIO
- Subjects
- *
PLANAR graphs , *PLANE geometry , *GRAPH theory , *POLYGONS , *TRIANGULATION - Abstract
We show that every plane graph admits a planar straight-line drawing in which all faces with more than three vertices are nonconvex polygons. [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
7. Testing the planar straight-line realizability of 2-trees with prescribed edge lengths.
- Author
-
Alegría, Carlos, Borrazzo, Manuel, Da Lozzo, Giordano, Di Battista, Giuseppe, Frati, Fabrizio, and Patrignani, Maurizio
- Subjects
- *
NP-hard problems , *COMPUTATIONAL complexity , *WEIGHTED graphs , *PLANAR graphs - Abstract
We study a classic problem introduced thirty years ago by Eades and Wormald. Let G = (V , E , λ) be a weighted planar graph, where λ : E → R + is a length function. The Fixed Edge-Length Planar Realization problem (FEPR for short) asks whether there exists a planar straight-line realization of G , i.e., a planar straight-line drawing of G where the Euclidean length of each edge e ∈ E is λ (e). Cabello, Demaine, and Rote showed that the FEPR problem is NP-hard, even when λ assigns the same value to all the edges and the graph is triconnected. Since the existence of large triconnected minors is crucial to the known NP-hardness proofs, in this paper we investigate the computational complexity of the FEPR problem for weighted 2-trees, which are K 4 -minor free. We show the NP-hardness of the problem, even when λ assigns to the edges only up to four distinct lengths. Conversely, we show that the FEPR problem is linear-time solvable when λ assigns to the edges up to two distinct lengths, or when the input has a prescribed embedding. Furthermore, we consider the FEPR problem for weighted maximal outerplanar graphs and prove it to be linear-time solvable if their dual tree is a path, and cubic-time solvable if their dual tree is a caterpillar. Finally, we prove that the FEPR problem for weighted 2-trees is slice-wise polynomial in the length of the large path. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
8. Relaxing the constraints of clustered planarity.
- Author
-
Angelini, Patrizio, Da Lozzo, Giordano, Di Battista, Giuseppe, Frati, Fabrizio, Patrignani, Maurizio, and Roselli, Vincenzo
- Subjects
- *
GRAPH theory , *CLUSTER analysis (Statistics) , *PLANE geometry , *COMPUTATIONAL complexity , *POLYNOMIAL time algorithms , *CONSTRAINT algorithms - Abstract
In a drawing of a clustered graph vertices and edges are drawn as points and curves, respectively, while clusters are represented by simple closed regions. A drawing of a clustered graph is c-planar if it has no edge–edge, edge–region, or region–region crossings. Determining the complexity of testing whether a clustered graph admits a c-planar drawing is a long-standing open problem in the Graph Drawing research area. An obvious necessary condition for c-planarity is the planarity of the graph underlying the clustered graph. However, this condition is not sufficient and the consequences on the problem due to the requirement of not having edge–region and region–region crossings are not yet fully understood. In order to shed light on the c-planarity problem, we consider a relaxed version of it, where some kinds of crossings (either edge–edge, edge–region, or region–region) are allowed even if the underlying graph is planar. We investigate the relationships among the minimum number of edge–edge, edge–region, and region–region crossings for drawings of the same clustered graph. Also, we consider drawings in which only crossings of one kind are admitted. In this setting, we prove that drawings with only edge–edge or with only edge–region crossings always exist, while drawings with only region–region crossings may not. Further, we provide upper and lower bounds for the number of such crossings. Finally, we give a polynomial-time algorithm to test whether a drawing with only region–region crossings exists for biconnected graphs, hence identifying a first non-trivial necessary condition for c-planarity that can be tested in polynomial time for a noticeable class of graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
9. Topological morphing of planar graphs.
- Author
-
Angelini, Patrizio, Cortese, Pier Francesco, Di Battista, Giuseppe, and Patrignani, Maurizio
- Subjects
- *
MORPHING (Computer animation) , *PLANAR graphs , *TOPOLOGICAL embeddings , *COMPUTER users , *PARAMETER estimation , *POLYNOMIAL time algorithms - Abstract
Abstract: In this paper we analyze the relationships among different planar embeddings of the same graph and study how two planar embeddings can be morphed one into the other with the minimum number of elementary changes, while preserving the mental map of the user. We call this problem Topological Morphing, in analogy with the well-known Geometric Morphing problem, in which it is studied how two planar drawings can be morphed one into the other with the minimum number of elementary changes. First, we define two operations, called flip and skip, describing natural transformations of a graph embedding that preserve the mental map of the user. Then, we study the problem of performing a morph while minimizing the number of these operations. We show that the Topological Morphing problem is NP-hard for biconnected planar graphs, we give polynomial-time algorithms for some restricted versions of the problem, and, based on such polynomial-time algorithms, we give a fixed-parameter tractable algorithm for the general case. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
10. Simple k-planar graphs are simple (k + 1)-quasiplanar.
- Author
-
Angelini, Patrizio, Bekos, Michael A., Brandenburg, Franz J., Da Lozzo, Giordano, Di Battista, Giuseppe, Didimo, Walter, Hoffmann, Michael, Liotta, Giuseppe, Montecchiani, Fabrizio, Rutter, Ignaz, and Tóth, Csaba D.
- Subjects
- *
PLANAR graphs , *EDGES (Geometry) - Abstract
A simple topological graph is k -quasiplanar (k ≥ 2) if it contains no k pairwise crossing edges, and k -planar if no edge is crossed more than k times. In this paper, we explore the relationship between k -planarity and k -quasiplanarity to show that, for k ≥ 2 , every k -planar simple topological graph can be transformed into a (k + 1) -quasiplanar simple topological graph. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
11. How to Morph Planar Graph Drawings
- Author
-
Timothy M. Chan, Anna Lubiw, Fidel Barrera-Cruz, Fabrizio Frati, Giuseppe Di Battista, Giordano Da Lozzo, Bryan T. Wilkinson, Patrizio Angelini, Vincenzo Roselli, Penny Haxell, Soroush Alamdari, Maurizio Patrignani, Sahil Singla, Alamdari, Soroush, Angelini, Patrizio, Barrera Cruz, Fidel, Chan, Timothy M., DA LOZZO, Giordano, DI BATTISTA, Giuseppe, Frati, Fabrizio, Haxell, Penny, Lubiw, Anna, Patrignani, Maurizio, Roselli, Vincenzo, Singla, Sahil, and Wilkinson, Bryan T.
- Subjects
Computational Geometry (cs.CG) ,FOS: Computer and information sciences ,Vertex (graph theory) ,General Computer Science ,Planar straight-line graph ,General Mathematics ,68R10 ,Constant speed ,INTERPOLATION ,0102 computer and information sciences ,02 engineering and technology ,Computer Science::Computational Geometry ,01 natural sciences ,Combinatorics ,symbols.namesake ,Continuous transformation ,Planar ,0202 electrical engineering, electronic engineering, information engineering ,ComputingMethodologies_COMPUTERGRAPHICS ,Mathematics ,Discrete mathematics ,TRIANGULATIONS ,transformation ,Planarity testing ,planar graphs ,Planar graph ,010201 computation theory & mathematics ,Exponential number ,symbols ,Computer Science - Computational Geometry ,020201 artificial intelligence & image processing ,morph ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
Given an $n$-vertex graph and two straight-line planar drawings of the graph that have the same faces and the same outer face, we show that there is a morph (i.e., a continuous transformation) between the two drawings that preserves straight-line planarity and consists of $O(n)$ steps, which we prove is optimal in the worst case. Each step is a unidirectional linear morph, which means that every vertex moves at constant speed along a straight line, and the lines are parallel although the vertex speeds may differ. Thus we provide an efficient version of Cairns' 1944 proof of the existence of straight-line planarity-preserving morphs for triangulated graphs, which required an exponential number of steps., Comment: 31 pages, 18 figures
- Published
- 2017
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.