29 results on '"Liotta, Giuseppe"'
Search Results
2. A Survey on Graph Drawing Beyond Planarity.
- Author
-
DIDIMO, WALTER, LIOTTA, GIUSEPPE, and MONTECCHIANI, FABRIZIO
- Subjects
- *
REPRESENTATIONS of graphs , *PLANAR graphs , *GRAPH algorithms , *GRAPH theory - Abstract
Graph Drawing Beyond Planarity is a rapidly growing research area that classifies and studies geometric representations of nonplanar graphs in terms of forbidden crossing configurations. The aim of this survey is to describe the main research directions in this area, the most prominent known results, and some of the most challenging open problems. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
3. Ortho-polygon Visibility Representations of Embedded Graphs.
- Author
-
Di Giacomo, Emilio, Didimo, Walter, Evans, William S., Liotta, Giuseppe, Meijer, Henk, Montecchiani, Fabrizio, and Wismath, Stephen K.
- Subjects
GRAPH theory ,REPRESENTATIONS of graphs ,EMBEDDINGS (Mathematics) ,PATHS & cycles in graph theory ,POLYNOMIAL time algorithms - Abstract
An ortho-polygon visibility representation of an
n -vertex embedded graphG (OPVR ofG ) is an embedding-preserving drawing ofG that maps every vertex to a distinct orthogonal polygon and each edge to a vertical or horizontal visibility between its end-vertices. The vertex complexity of an OPVR ofG is the minimumk such that every polygon has at mostk reflex corners. We present polynomial time algorithms that test whetherG has an OPVR and, if so, compute one of minimum vertex complexity. We argue that the existence and the vertex complexity of an OPVR ofG are related to its number of crossings per edge and to its connectivity. More precisely, we prove that ifG has at most one crossing per edge (i.e.,G is a 1-plane graph), an OPVR ofG always exists while this may not be the case if two crossings per edge are allowed. Also, ifG is a 3-connected 1-plane graph, we can compute an OPVR ofG whose vertex complexity is bounded by a constant inO (n ) time. However, ifG is a 2-connected 1-plane graph, the vertex complexity of any OPVR ofG may be Ω(n). In contrast, we describe a family of 2-connected 1-plane graphs for which an embedding that guarantees constant vertex complexity can be computed in O (n ) time. Finally, we present the results of an experimental study on the vertex complexity of ortho-polygon visibility representations of 1-plane graphs. [ABSTRACT FROM AUTHOR]- Published
- 2018
- Full Text
- View/download PDF
4. On the Planar Split Thickness of Graphs.
- Author
-
Eppstein, David, Kindermann, Philipp, Kobourov, Stephen, Liotta, Giuseppe, Lubiw, Anna, Maignan, Aude, Mondal, Debajyoti, Vosoughpour, Hamideh, Whitesides, Sue, and Wismath, Stephen
- Subjects
BIPARTITE graphs ,GEOMETRIC vertices ,APPROXIMATION theory ,COMPLETE graphs ,VISUALIZATION - Abstract
Motivated by applications in graph drawing and information visualization, we examine the planar split thickness of a graph, that is, the smallest
k such that the graph isk -splittable into a planar graph. Ak -split operation substitutes a vertexv by at mostk new vertices such that each neighbor ofv is connected to at least one of the new vertices. We first examine the planar split thickness of complete graphs, complete bipartite graphs, multipartite graphs, bounded degree graphs, and genus-1 graphs. We then prove that it is NP-hard to recognize graphs that are 2-splittable into a planar graph, and show that one can approximate the planar split thickness of a graph within a constant factor. If the treewidth is bounded, then we can even verifyk -splittability in linear time, for a constantk . [ABSTRACT FROM AUTHOR]- Published
- 2018
- Full Text
- View/download PDF
5. An annotated bibliography on 1-planarity.
- Author
-
Kobourov, Stephen G., Liotta, Giuseppe, and Montecchiani, Fabrizio
- Subjects
PLANAR graphs ,GRAPH theory ,GRAPHIC methods ,GRAPH algorithms ,ANNOTATIONS - Abstract
The notion of 1-planarity is among the most natural and most studied generalizations of graph planarity. A graph is 1-planar if it has an embedding where each edge is crossed by at most another edge. The study of 1-planar graphs dates back to more than fifty years ago and, recently, it has driven increasing attention in the areas of graph theory, graph algorithms, graph drawing, and computational geometry. This annotated bibliography aims to provide a guiding reference to researchers who want to have an overview of the large body of literature about 1-planar graphs. It reviews the current literature covering various research streams about 1-planarity, such as characterization and recognition, combinatorial properties, and geometric representations. As an additional contribution, we offer a list of open problems on 1-planar graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
6. Drawings of Graphs
- Author
-
Liotta, Giuseppe and Tamassia, R.
- Subjects
graph theory - Published
- 2004
7. 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
8. The Approximate Rectangle of Influence Drawability Problem.
- Author
-
Di Giacomo, Emilio, Liotta, Giuseppe, and Meijer, Henk
- Subjects
- *
APPROXIMATION theory , *PROBLEM solving , *NEGATIVE numbers , *GRAPH theory , *FACTOR analysis , *PLANAR graphs - Abstract
Let ε, ε be two non negative numbers. An approximate rectangle of influence drawing (also called ( ε, ε)-RID) is a proximity drawing of a graph such that: (i) if u, v are adjacent vertices then their rectangle of influence 'scaled down' by the factor $\frac{1}{1+\varepsilon_{1}}$ does not contain other vertices of the drawing; (ii) if u, v are not adjacent, then their rectangle of influence 'blown-up' by the factor 1+ ε contains some vertices of the drawing other than u and v. Firstly, we prove that all planar graphs have an ( ε, ε)-RID for any ε>0 and ε>0, while there exist planar graphs which do not admit an ( ε,0)-RID and planar graphs which do not admit a (0, ε)-RID. Then, we investigate (0, ε)-RIDs; we prove that both the outerplanar graphs and a suitably defined family of graphs without separating 3-cycles admit this type of drawing. Finally, we study polynomial area approximate rectangle of influence drawings and prove that (0, ε)-RIDs of proper track planar graphs (a superclass of the outerplanar graphs) can be computed in polynomial area for any ε>2. As for values of ε such that ε≤2, we describe a drawing algorithm that computes (0, ε)-RIDs of binary trees in area $O(n^{c + f(\varepsilon_{2})})$, where c is a positive constant, f( ε) is a poly-logarithmic function that tends to infinity as ε tends to zero, and n is the number of vertices of the input tree. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
9. PROXIMITY DRAWINGS OF HIGH-DEGREE TREES.
- Author
-
HURTADO, FERRAN, LIOTTA, GIUSEPPE, and WOOD, DAVID R.
- Subjects
- *
SPANNING trees , *GRAPH theory , *COMPUTATIONAL geometry , *TREE graphs , *GRAPHIC methods - Abstract
A drawing of a given (abstract) tree that is a minimum spanning tree of the vertex set is considered aesthetically pleasing. However, such a drawing can only exist if the tree has maximum degree at most 6. What can be said for trees of higher degree? We approach this question by supposing that a partition or covering of the tree by subtrees of bounded degree is given. Then we show that if the partition or covering satisfies some natural properties, then there is a drawing of the entire tree such that each of the given subtrees is drawn as a minimum spanning tree of its vertex set. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
10. 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
11. UPWARD SPIRALITY AND UPWARD PLANARITY TESTING.
- Author
-
Didimo, Walter, Giordano, Francesco, and Liotta, Giuseppe
- Subjects
ALGORITHMS ,GRAPH theory ,GRAPHIC methods ,MATHEMATICAL analysis ,PLANE geometry ,NUMBER theory - Abstract
A digraph is upward planar if it admits a planar drawing where all edges are monotone in the upward direction. It is known that the problem of testing a digraph for upward planarity is NP-complete in general. This paper describes an O(n
4 )-time upward planarity testing algorithm for all digraphs that have a series-parallel structure, where n is the number of vertices of the input. This significantly enlarges the family of digraphs for which a polynomial-time testing algorithm is known. Furthermore, the study is extended to general digraphs, and a fixed parameter tractable algorithm for upward planarity testing is described, whose time complexity is O(dt · t · n3 + d · t2 · n + d2 · n2 ) where t is the number of triconnected components of the digraph and d is an upper bound on the diameter of any split component of the digraph. Our results use the new notion of upward spirality that, informally speaking, is a measure of the "level of winding" that a triconnected component of a digraph G can have in an upward planar drawing of G. [ABSTRACT FROM AUTHOR]- Published
- 2009
- Full Text
- View/download PDF
12. 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
13. SIMULTANEOUS EMBEDDING OF OUTERPLANAR GRAPHS, PATHS, AND CYCLES.
- Author
-
DI GIACOMO, EMILIO, LIOTTA, GIUSEPPE, and Goodrich, M. T.
- Subjects
- *
EMBEDDINGS (Mathematics) , *ALGEBRAIC geometry , *HAMILTONIAN graph theory , *GRAPH theory , *ALGEBRA - Abstract
Let G1 and G2 be two planar graphs having some vertices in common. A simultaneous embedding of G1 and G2 is a pair of crossing-free drawings of G1 and G2 such that each vertex in common is represented by the same point in both drawings. In this paper we show that an outerplanar graph and a simple path can be simultaneously embedded with fixed edges such that the edges in common are straight-line segments while the other edges of the outerplanar graph can have at most one bend per edge. We then exploit the technique for outerplanar graphs and paths to study simultaneous embeddings of other pairs of graphs. Namely, we study simultaneous embedding with fixed edges of: (i) two outerplanar graphs sharing a forest of paths and (ii) an outerplanar graph and a cycle. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
14. ON EMBEDDING A GRAPH ON TWO SETS OF POINTS.
- Author
-
DI GIACOMO, EMILIO, LIOTTA, GIUSEPPE, TROTTA, FRANCESCO, and Seok-Hee Hong
- Subjects
- *
GRAPH theory , *EMBEDDINGS (Mathematics) , *ALGEBRAIC geometry , *GRAPHIC methods , *POINT set theory , *ALGEBRA - Abstract
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 are blue. A bichromatic point-set embedding of G on R ∪ B is a crossing-free drawing of G such that each blue vertex is mapped to a point of B, each red vertex is mapped to a point of R, and each edge is a polygonal curve. We study the curve complexity of bichromatic point-set embeddings; i.e., the number of bends per edge that are necessary and sufficient to compute such drawings. We show that O(n) bends are sometimes necessary. We also prove that two bends per edge suffice if G is a 2-colored caterpillar and that for properly 2-colored caterpillars, properly 2-colored wreaths, 2-colored paths, and 2-colored cycles the number of bends per edge can be reduced to one, which is worst-case optimal. [ABSTRACT FROM AUTHOR]
- Published
- 2006
- Full Text
- View/download PDF
15. Drawing Directed Acyclic Graphs: An Experimental Study.
- Author
-
Di Battista, Giuseppe, Garg, Ashim, Liotta, Giuseppe, Parise, Armando, Tamassia, Roberto, Tassinari, Emanuele, Vargiu, Francesco, Vismara, Luca, and Kirkpatrick, D. G.
- Subjects
GRAPH theory ,ALGORITHMS ,TOPOLOGY - Abstract
In this paper we consider the important class of directed acyclic graphs (DAGs), and present the results of a comparative study on four popular drawing algorithms specifically developed for them. The study has been performed within a general experimental setting consisting of two large test suites of DAGs and a set of quality measures. The focus of the experiments has been the practical behavior of the algorithms with a geometric foundation compared to that of the algorithms with a topological foundation. The four algorithms exhibit various trade-offs with respect to the quality measures considered, and none of them clearly outperforms the others. Our analysis has motivated the development of a new hybrid strategy for drawing DAGs that performs quite well in practice. [ABSTRACT FROM AUTHOR]
- Published
- 2000
- Full Text
- View/download PDF
16. 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
17. 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
18. 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
19. Techniques for Edge Stratification of Complex Graph Drawings.
- Author
-
Di Giacomo, Emilio, Didimo, Walter, Liotta, Giuseppe, Montecchiani, Fabrizio, and Tollis, Ioannis G.
- Subjects
- *
MATHEMATICAL complex analysis , *GRAPH theory , *COMPUTER algorithms , *COMPUTER users , *HEURISTIC algorithms - Abstract
Abstract: We propose an approach that allows a user (e.g., an analyst) to explore a layout produced by any graph drawing algorithm, in order to reduce the visual complexity and clarify its presentation. Our approach is based on stratifying the drawing into layers with desired properties; to this aim, heuristics are presented. The produced layers can be explored and combined by the user to gradually acquire details. We present a user study to test the effectiveness of our approach. Furthermore, we performed an experimental analysis on popular force-directed graph drawing algorithms, in order to evaluate what is the algorithm that produces the smallest number of layers and if there is any correlation between the number of crossings and the number of layers of a graph layout. The proposed approach is useful to explore graph layouts, as confirmed by the presented user study. Furthermore, interesting considerations arise from the experimental evaluation, in particular, our results suggest that the number of layers of a graph layout may represent a reliable measure of its visual complexity. The algorithms presented in this paper can be effectively applied to graph layouts with a few hundreds of edges and vertices. For larger drawings that contain lots of crossings, the time complexity of our algorithms grows quadratically in the number of edges and more efficient techniques need to be devised. The proposed approach takes as input a layout produced by any graph drawing algorithm, therefore it can be applied in a variety of application domains. Several research directions can be explored to extend our framework and to devise new visualization paradigms to effectively present stratified drawings. [Copyright &y& Elsevier]
- Published
- 2014
- Full Text
- View/download PDF
20. 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
21. 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
22. 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
23. 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
24. -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
25. 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
26. [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
27. 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
28. 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
29. 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.