12 citations · 57 across the 39 of their papers we have counts for
22 papers · 1 filter
Axis-Parallel Right Angle Crossing Graphs
Patrizio Angelini, Michael A. Bekos, Julia Katheder +3
A RAC graph is one admitting a RAC drawing, that is, a polyline drawing in which each crossing occurs at a right angle. Originally motivated by psychological studies on readability…
Recognizing Map Graphs of Bounded Treewidth
Patrizio Angelini, Michael A. Bekos, Giordano Da Lozzo +3
A map graph is a graph admitting a representation in which vertices are nations on a spherical map and edges are shared curve segments or points between nations. We present an expl…
On Upward-Planar L-Drawings of Graphs
Patrizio Angelini, Steven Chaplick, Sabine Cornelsen +1
In an upward-planar L-drawing of a directed acyclic graph (DAG) each edge is represented as a polyline composed of a vertical segment with its lowest endpoint at the tail of $e…
2-Level Quasi-Planarity or How Caterpillars Climb (SPQR-)Trees
Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista +2
Given a bipartite graph , the -Level Quasi-Planarity problem asks for the existence of a drawing of in the plane such that the vertices in and in …
Efficient Generation of Different Topological Representations of Graphs Beyond-Planarity
Patrizio Angelini, Michael A. Bekos, Michael Kaufmann +1
Beyond-planarity focuses on combinatorial properties of classes of non-planar graphs that allow for representations satisfying certain local geometric or topological constraints on…
The QuaSEFE Problem
Patrizio Angelini, Henry Förster, Michael Hoffmann +4
We initiate the study of Simultaneous Graph Embedding with Fixed Edges in the beyond planarity framework. In the QuaSEFE problem, we allow edge crossings, as long as each graph ind…
On RAC Drawings of Graphs with one Bend per Edge
Patrizio Angelini, Michael A. Bekos, Henry Förster +1
A k-bend right-angle-crossing drawing or (k-bend RAC drawing}, for short) of a graph is a polyline drawing where each edge has at most k bends and the angles formed at the crossing…
Turning Cliques into Paths to Achieve Planarity
Patrizio Angelini, Peter Eades, Seok-Hee Hong +5
Motivated by hybrid graph representations, we introduce and study the following beyond-planarity problem, which we call -Clique2Path Planarity: Given a graph , whose vertices…
Multi-Level Steiner Trees
Reyan Ahmed, Patrizio Angelini, Faryad Darabi Sahneh +8
In the classical Steiner tree problem, given an undirected, connected graph with non-negative edge costs and a set of \emph{terminals} , the objective is to…
On Vertex- and Empty-Ply Proximity Drawings
Patrizio Angelini, Steven Chaplick, Felice De Luca +7
We initiate the study of the vertex-ply of straight-line drawings, as a relaxation of the recently introduced ply number. Consider the disks centered at each vertex with radius equ…
Hierarchical Partial Planarity
Patrizio Angelini, Michael A. Bekos
In this paper we consider graphs whose edges are associated with a degree of {\em importance}, which may depend on the type of connections they represent or on how recently they ap…
Clustered Planarity with Pipes
Patrizio Angelini, Giordano Da Lozzo
We study the version of the C-Planarity problem in which edges connecting the same pair of clusters must be grouped into pipes, which generalizes the Strip Planarity problem. We gi…
Low Ply Drawings of Trees
Patrizio Angelini, Michael A. Bekos, Till Bruckdorfer +5
We consider the recently introduced model of \emph{low ply graph drawing}, in which the ply-disks of the vertices do not have many common overlaps, which results in a good distribu…
Vertex-Coloring with Star-Defects
Patrizio Angelini, Michael A. Bekos, Michael Kaufmann +1
Defective coloring is a variant of traditional vertex-coloring, according to which adjacent vertices are allowed to have the same color, as long as the monochromatic components ind…
Beyond Level Planarity
Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista +3
In this paper we settle the computational complexity of two open problems related to the extension of the notion of level planarity to surfaces different from the plane. Namely, we…
L-Drawings of Directed Graphs
Patrizio Angelini, Giordano Da Lozzo, Marco Di Bartolomeo +4
We introduce L-drawings, a novel paradigm for representing directed graphs aiming at combining the readability features of orthogonal drawings with the expressive power of matrix r…
Intersection-Link Representations of Graphs
Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista +3
We consider drawings of graphs that contain dense subgraphs. We introduce intersection-link representations for such graphs, in which each vertex is represented by a geometric…
On the Complexity of Clustered-Level Planarity and T-Level Planarity
Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista +2
In this paper we study two problems related to the drawing of level graphs, that is, T-LEVEL PLANARITY and CLUSTERED-LEVEL PLANARITY. We show that both problems are NP-complete in…
Morphing Planar Graph Drawings Optimally
Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista +3
We provide an algorithm for computing a planar morph between any two planar straight-line drawings of any -vertex plane graph in morphing steps, thus improving upon the p…
SEFE with No Mapping via Large Induced Outerplane Graphs in Plane Graphs
Patrizio Angelini, William Evans, Fabrizio Frati +1
We show that every -vertex planar graph admits a simultaneous embedding with no mapping and with fixed edges with any -vertex planar graph. In order to achieve this resul…
Testing Mutual Duality of Planar Graphs
Patrizio Angelini, Thomas Bläsius, Ignaz Rutter
We introduce and study the problem \mpd, which asks for two planar graphs and whether can be embedded such that its dual is isomorphic to . Our algorithmic m…
Implementing a Partitioned 2-page Book Embedding Testing Algorithm
Patrizio Angelini, Marco Di Bartolomeo, Giuseppe Di Battista
In a book embedding the vertices of a graph are placed on the "spine" of a "book" and the edges are assigned to "pages" so that edges on the same page do not cross. In the Partitio…