8 results on '"LIOTTA, GIUSEPPE"'
Search Results
2. Lower and upper bounds for long induced paths in 3-connected planar graphs.
- Author
-
Di Giacomo, Emilio, Liotta, Giuseppe, and Mchedlidze, Tamara
- Subjects
- *
MATHEMATICAL bounds , *PLANAR graphs , *PATHS & cycles in graph theory , *GEOMETRIC vertices , *MATHEMATICAL inequalities , *SUBGRAPHS - Abstract
Let G be a 3-connected planar graph with n vertices and let p ( G ) be the maximum number of vertices of an induced subgraph of G that is a path. Substantially improving previous results, we prove that p ( G ) ≥ log n 12 log log n . To demonstrate the tightness of this bound, we notice that the above inequality implies p ( G ) ∈ Ω ( ( log 2 n ) 1 − ε ) , where ε is any positive constant smaller than 1, and describe an infinite family of planar graphs for which p ( G ) ∈ O ( log n ) . As a byproduct of our research, we prove a result of independent interest: Every 3-connected planar graph with n vertices contains an induced subgraph that is outerplanar and connected and that contains at least n 3 vertices. The proofs in the paper are constructive and give rise to O ( n ) -time algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
3. (k,p)-planarity: A relaxation of hybrid planarity.
- Author
-
Di Giacomo, Emilio, Lenhart, William J., Liotta, Giuseppe, Randolph, Timothy W., and Tappini, Alessandra
- Subjects
- *
PLANAR graphs , *NP-complete problems , *EDGES (Geometry) - Abstract
We present a new model for hybrid planarity that relaxes existing hybrid representation models. A graph G = (V , E) is (k , p) -planar if V can be partitioned into clusters of size at most k such that G admits a drawing where: (i) each cluster is associated with a closed, bounded planar region, called a cluster region ; (ii) cluster regions are pairwise disjoint, (iii) each vertex v ∈ V is identified with at most p distinct points, called ports , on the boundary of its cluster region; (iv) each inter-cluster edge (u , v) ∈ E is identified with a Jordan arc connecting a port of u to a port of v ; (v) inter-cluster edges do not cross or intersect cluster regions except at their end-points. We first tightly bound the number of edges in a (k , p) -planar graph with p < k. We then prove that (4 , 1) -planarity testing and (2 , 2) -planarity testing are NP-complete problems. Finally, we prove that neither the class of (2 , 2) -planar graphs nor the class of 1-planar graphs contains the other, indicating that the (k , p) -planar graphs are a large and novel class. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
4. 2-colored point-set embeddings of partial 2-trees.
- Author
-
Di Giacomo, Emilio, Hančl, Jaroslav, and Liotta, Giuseppe
- Subjects
- *
PLANAR graphs , *POINT set theory , *CATERPILLARS - Abstract
• For n ≥ 14 there is a properly 2-colored SP-graph with 2 n + 4 vertices s.t. any 2-colored PSE requires Ω (n) bends on Ω (n) edges • 2 bends per edge suffice for a 2-colored PSE of properly 2-colored outerplanar graphs • 1 bend per edge suffices for a 2-colored PSE of a properly 2-colored outerplanar graph if the points are linearly separable • 3 bends per edge suffice for a 2-colored PSE of a 2-colored outerplanar graph • 1 bend per edge suffices for a 2-colored PSE of a 2-colored caterpillar Let G be a planar graph whose vertices are colored either red or blue and let S be a set of points having as many red (resp. blue) points as the red (resp. blue) vertices of G. A 2-colored point-set embedding of G on S is a planar drawing that maps each red (resp. blue) vertex of G to a red (resp. blue) point of S. We show that there exist partial 2-trees that are properly 2-colored (i.e., they are 2-colored with no two adjacent vertices have the same color), whose point-set embeddings may require linearly many bends on linearly many edges. For a contrast, we show that two bends per edge are sufficient for 2-colored point-set embedding of properly 2-colored outerplanar graphs. For separable point sets this bound reduces to one, which is worst-case optimal. If the 2-coloring of the outerplanar graph is not proper, three bends per edge are sufficient and one bend per edge (which is worst-case optimal) is sufficient for caterpillars. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
5. On the edge-length ratio of outerplanar graphs.
- Author
-
Lazard, Sylvain, Lenhart, William J., and Liotta, Giuseppe
- Subjects
- *
PLANAR graphs , *RATIO & proportion , *COMPUTATIONAL geometry - Abstract
Abstract We show that any outerplanar graph admits a planar straight-line drawing such that the length ratio of the longest to the shortest edges is strictly less than 2. This result is tight in the sense that for any ϵ > 0 there are outerplanar graphs that cannot be drawn with an edge-length ratio smaller than 2 − ϵ. We also show that this ratio cannot be bounded if the embeddings of the outerplanar graphs are given. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- 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. Recognizing and drawing IC-planar graphs.
- Author
-
Brandenburg, Franz J., Didimo, Walter, Evans, William S., Kindermann, Philipp, Liotta, Giuseppe, and Montecchiani, Fabrizio
- Subjects
- *
PLANAR graphs , *EDGES (Geometry) , *NP-hard problems , *POLYNOMIAL time algorithms , *RIGHT angle - Abstract
We give new results about the relationship between 1-planar graphs and RAC graphs . A graph is 1-planar if it has a drawing where each edge is crossed at most once. A graph is RAC if it can be drawn in such a way that its edges cross only at right angles. These two classes of graphs and their relationships have been widely investigated in the last years, due to their relevance in application domains where computing readable graph layouts is important to analyze or design relational data sets. We study IC-planar graphs , the sub-family of 1-planar graphs that admit 1-planar drawings with independent crossings (i.e., no two crossed edges share an endpoint). We prove that every IC-planar graph admits a straight-line RAC drawing, which may require however exponential area. If we do not require right angle crossings, we can draw every IC-planar graph with straight-line edges in linear time and quadratic area. We then study the problem of testing whether a graph is IC-planar. We prove that this problem is NP-hard, even if a rotation system for the graph is fixed. On the positive side, we describe a polynomial-time algorithm that tests whether a triangulated plane graph augmented with a given set of edges that form a matching is IC-planar. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
8. 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
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.