Patrizio Angelini

Dr. Patrizio Angelini

John Cabot University (Rome)
orcid

Research Focus & Metrics

Academic Career Length

20Years (2007-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
13 April 2015 in ACM Transactions on Algorithms
Verified
Journal Article
Open access
PAPatrizio Angelini
Patrizio Angelini
GBGiuseppe Di Battista
Giuseppe Di Battista
FFFabrizio Frati
Fabrizio Frati
VJVít Jelínek
Vít Jelínek
JKJan Kratochvíl
Jan Kratochvíl
IRIgnaz Rutter
Ignaz Rutter
We study the following problem: given a planar graph G and a planar drawing (embedding) of a subgraph of G , can such a drawing be extended to a planar drawing of the entire graph G ? This problem fits the paradigm of extending a partial solution for a problem to a complete one, which has been studied before in many different settings. Unlike many cases, in which the presence of a partial solution in the input makes an otherwise easy problem hard, we show that the planarity question remains polynomial-time solvable. Our algorithm is based on several combinatorial lemmas, which show that the planarity of partially embedded graphs exhibits the ‘TONCAS’ behavior “the obvious necessary conditions for planarity are also sufficient.” These conditions are expressed in terms of the interplay between (1) the rotation system and containment relationships between cycles and (2) the decomposition of a graph into its connected, biconnected, and triconnected components. This implies that no dynamic programming is needed for a decision algorithm and that the elements of the decomposition can be processed independently. Further, by equipping the components of the decomposition with suitable data structures and by carefully splitting the problem into simpler subproblems, we make our algorithm run in linear time. Finally, we consider several generalizations of the problem, such as minimizing the number of edges of the partial embedding that need to be rerouted to extend it, and argue that they are NP-hard. We also apply our algorithm to the simultaneous graph drawing problem Simultaneous Embedding with Fixed Edges (Sefe) . There we obtain a linear-time algorithm for the case that one of the input graphs or the common graph has a fixed planar embedding.

1 July 2012 in Journal of Discrete Algorithms
Verified
Journal Article
Closed access
PAPatrizio Angelini
Patrizio Angelini
GBGiuseppe Di Battista
Giuseppe Di Battista
FFFabrizio Frati
Fabrizio Frati
MPMaurizio Patrignani
Maurizio Patrignani
IRIgnaz Rutter
Ignaz Rutter

1 January 2010 in Journal of Graph Algorithms and Applications
Verified
Journal Article
Closed access
PAPatrizio Angelini
Patrizio Angelini
FFFabrizio Frati
Fabrizio Frati
LGLuca Grilli
Luca Grilli

1 January 2017 in SIAM Journal on Computing
Verified
Journal Article
Closed access
SASoroush Alamdari
Soroush Alamdari
PAPatrizio Angelini
Patrizio Angelini
FBFidel Barrera-Cruz
Fidel Barrera-Cruz
TCTimothy M. Chan
Timothy M. Chan
GLGiordano Da Lozzo
Giordano Da Lozzo
BWBryan T. Wilkinson
Bryan T. Wilkinson
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) betw...

1 January 2012 in Journal of Graph Algorithms and Applications
Verified
Journal Article
Closed access
PAPatrizio Angelini
Patrizio Angelini
ECEnrico Colasante
Enrico Colasante
GBGiuseppe Di Battista
Giuseppe Di Battista
FFFabrizio Frati
Fabrizio Frati
MPMaurizio Patrignani
Maurizio Patrignani

1 January 2011 in Journal of Graph Algorithms and Applications
Verified
Journal Article
Closed access
PAPatrizio Angelini
Patrizio Angelini
LCLuca Cittadini
Luca Cittadini
WDWalter Didimo
Walter Didimo
FFFabrizio Frati
Fabrizio Frati
GBGiuseppe Di Battista
Giuseppe Di Battista
ASAntonios Symvonis
Antonios Symvonis
Special Issue on Selected Papers from GD '09