Maurizio Patrignani's Publications

Maurizio Patrignani

Home

Research groups:
  Graph Drawing
  Computer Networks

Publications:
  By type
  By year
  By topic

Teaching:
  Courses (Italian)
  Theses & Labs


Best Paper Award


42nd International Conference on Current Trends in Theory and Practice of Computer Science.
Harrachov, Czech Republic
Jan 23-28, 2016

We will be at


12nd Bertinoro Workshop on Graph Drawing

March 05-10, 2017

Show all news

Maurizio Patrignani's Publications

Interdomain Routing Stability

  1. Marco Chiesa, Giuseppe Di Battista, Thomas Erlebach, Maurizio Patrignani. Computational Complexity of Traffic Hijacking under BGP and S-BGP. In Proc. 39th International Colloquium on Automata, Languages and Programming (ICALP '12), Springer Verlag, volume 7392 of Lecture Notes in Computer Science, pages 476-487, 2012. [see arXiv extended version] [ Presentation at ICALP'12]

  2. Luca Cittadini, Giuseppe Di Battista, Thomas Erlebach, Maurizio Patrignani, Massimo Rimondini. Assigning AS Relationships to Satisfy the Gao-Rexford Conditions. In Proc. ICNP 2010, IEEE, pages 113-123, 2010. [ Presentation at ICNP'10]

Morphing Graph Drawings

  1. Soroush Alamdari, Patrizio Angelini, Fidel Barrera-Cruz, Timothy M. Chan, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Penny Haxell, Anna Lubiw, Maurizio Patrignani, Vincenzo Roselli, Sahil Singla, Bryan T. Wilkinson. How to morph planar graph drawings. SIAM Journal on Computing. 46(2):824-852. 2017. [arXiv version]

  2. Soroush Alamdari, Patrizio Angelini, Fidel Barrera-Cruz, Timothy M. Chan, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Penny Haxell, Anna Lubiw, Maurizio Patrignani, Vincenzo Roselli, Sahil Singla, Bryan T. Wilkinson. How to morph planar graph drawings. Technical Report arXiv:1606.00425, Cornell University, 2016.

  3. Patrizio Angelini, Giordano Da Lozzo, Fabrizio Frati, Anna Lubiw, Maurizio Patrignani, Vincenzo Roselli. Optimal Morphs of Convex Drawings. In, Lars Arge, J\'anos Pach, editors, Proc. 31st Symposium on Computational Geometry (SoCG '15), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, volume 34 of LIPIcs, pages 126-140, 2015.

  4. Patrizio Angelini, Giordano Da Lozzo, Fabrizio Frati, Anna Lubiw, Maurizio Patrignani and Vincenzo Roselli. Optimal Morphs of Convex Drawings. Technical Report arXiv:1503.09021, Cornell University, 2015.

  5. Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani and Vincenzo Roselli. Morphing Planar Graph Drawings Optimally. In Proc. 41st International Colloquium on Automata, Languages and Programming (ICALP '14), Springer Verlag, volume 8572 of Lecture Notes in Computer Science, pages 126-137, 2014.

  6. Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani and Vincenzo Roselli. Morphing Planar Graph Drawings Optimally. Technical Report arXiv:1402.4364, Cornell University, 2014.

  7. Patrizio Angelini, Pier Francesco Cortese, Giuseppe Di Battista, Maurizio Patrignani. Topological Morphing of Planar Graphs. Theor. Computer Science. 514:2-20. 2013.

  8. Patrizio Angelini, Fabrizio Frati, Maurizio Patrignani, Vincenzo Roselli. Morphing Planar Graph Drawings Efficiently. In, Stephen Wismath, Alexander Wolff, editors, Proc. 21st International Symposium on Graph Drawing (GD '13), Springer-Verlag, volume 8242 of Lecture Notes in Computer Science, pages 49-60, 2013. [ presentation at GD'13]

  9. Patrizio Angelini, Fabrizio Frati, Maurizio Patrignani, Vincenzo Roselli. Morphing Planar Graph Drawings Efficiently. Technical Report arXiv:1308.4291, Cornell University, 2013.

  10. Soroush Alamdari, Patrizio Angelini, Timothy M. Chan, Giuseppe Di Battista, Fabrizio Frati, Anna Lubiw, Maurizio Patrignani, Vincenzo Roselli, Sahil Singla, Bryan T. Wilkinson. Morphing Planar Graph Drawings with a Polynomial Number of Steps. In 24th ACM-SIAM Symposium on Discrete Algorithms (SODA '13), pages 1656-1667, 2013. [ presentation at SODA'13]

  11. Patrizio Angelini, Pier Francesco Cortese, Giuseppe Di Battista, Maurizio Patrignani. Topological Morphing of Planar Graphs. Technical Report RT-DIA-134-2008, Dept. of Computer Science and Automation, Roma Tre University, 2008. [conference version]

  12. Patrizio Angelini, Pier Francesco Cortese, Giuseppe Di Battista, Maurizio Patrignani. Topological Morphing of Planar Graphs. In, Ioannis G. Tollis, Maurizio Patrignani, editors, 16th International Symposium on Graph Drawing (GD '08), Springer-Verlag, volume 5417 of Lecture Notes in Computer Science, pages 145-156, 2009. [see TR]

Clustered Graphs

  1. Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani. Computing NodeTrix Representations of Clustered Graphs. In, Martin Nöllenburg, Yifan Hu, editors, Proc. 24th International Symposium on Graph Drawing and Network Visualization (GD '16), Springer International Publishing, volume 9801 of Lecture Notes in Computer Science, pages 107-120, 2016.

  2. Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani. Computing NodeTrix Representations of Clustered Graphs. Technical Report arXiv:1608.08952, Cornell University, 2016.

  3. Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, Ignaz Rutter. Intersection-Link Representations of Graphs. Technical Report arXiv:1508.07557, Cornell University, 2015.

  4. Patrizio Angelini, Giordano Da Lozzo, Marco Di Bartolomeo, Giuseppe Di Battista, Seok-Hee Hong, Maurizio Patrignani, Vincenzo Roselli. Anchored Drawings of Planar Graphs. In, Christian Duncan, Antonios Symvonis, editors, Proc. 22nd International Symposium on Graph Drawing (GD '14), Springer-Verlag, volume 8871 of Lecture Notes in Computer Science, pages 404-415, 2014. [ presentation at GD'14]

  5. Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, Vincenzo Roselli. Relaxing the Constraints of Clustered Planarity. Computational Geometry: Theory and Applications. 48(2):42-75. 2015.

  6. Patrizio Angelini, Giordano Da Lozzo and Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, Vincenzo Roselli. Relaxing the Constraints of Clustered Planarity . Technical Report arXiv:1207.3934, Cornell University, 2012.

  7. Patrizio Angelini, Fabrizio Frati, Maurizio Patrignani. Splitting Clusters To Get C-Planarity. In, David Eppstein, Emden R. Gansner, editors, 17th International Symposium on Graph Drawing (GD '09), Springer-Verlag, volume 5849 of Lecture Notes in Computer Science, pages 57-68, 2010.

  8. Pier Francesco Cortese, Giuseppe Di Battista, Maurizio Patrignani, Maurizio Pizzonia. On Embedding a Cycle in a Plane Graph. Discrete Mathematics. 309(7):1856-1869. Apr 2009. [see TR] [conference version]

  9. Pier Francesco Cortese, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, Maurizio Pizzonia. C-Planarity of C-Connected Clustered Graphs. Journal of Graph Algorithms and Applications. 12(2):225-262. Nov 2008. [ download pdf] [see TR1] [see TR2]

  10. Pier Francesco Cortese, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, Maurizio Pizzonia. C-Planarity of C-Connected Clustered Graphs: Part I - Characterization. Technical Report RT-DIA-109-2006, Dip. Informatica e Automazione, Univ. Roma Tre, 2006. [journal version]

  11. Pier Francesco Cortese, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, Maurizio Pizzonia. C-Planarity of C-Connected Clustered Graphs: Part II - Testing and Embedding Algorithm. Technical Report RT-DIA-110-2006, Dip. Informatica e Automazione, Univ. Roma Tre, 2006. [journal version]

  12. Pier Francesco Cortese, Giuseppe Di Battista, Maurizio Patrignani, Maurizio Pizzonia. Clustering Cycles into Cycles of Clusters. Journal of Graph Algorithms and Applications. 9(3):391-413. 2005. Special Issue on the 2004 Symposium on Graph Drawing, GD '04. [see TR] [conference version]

  13. Pier Francesco Cortese, Giuseppe Di Battista, Maurizio Patrignani, Maurizio Pizzonia. On Embedding a Cycle in a Plane Graph. In, P. Healy, N.S. Nikolov, editors, 13th International Symposium on Graph Drawing (Proc. GD '05), Springer-Verlag, volume 3843 of Lecture Notes in Computer Science, pages 46-60, 2005. [see TR] [journal version]

  14. Pier Francesco Cortese, Giuseppe Di Battista, Maurizio Patrignani, Maurizio Pizzonia. On Embedding a Cycle in a Plane Graph. Technical Report RT-DIA-100-2005, Dip. Informatica e Automazione, Univ. Roma Tre, 2005. [conference version] [journal version]

  15. Pier Francesco Cortese, Giuseppe Di Battista, Maurizio Patrignani, Maurizio Pizzonia. Clustering Cycles into Cycles of Clusters. In 12th International Symposium on Graph Drawing (Proc. GD '04), Springer-Verlag, volume 3383 of Lecture Notes in Computer Science, pages 100-110, 2004. [ preliminary version] [see TR] [journal version]

  16. Pier Francesco Cortese, Giuseppe Di Battista, Maurizio Patrignani, Maurizio Pizzonia. Clustering Cycles into Cycles of Clusters. Technical Report RT-DIA-91-2004, Dip. Informatica e Automazione, Univ. Roma Tre, 2004. [conference version] [journal version]

Orthogonal Drawings

  1. Walter Didimo, Giuseppe Liotta, Maurizio Patrignani. On the Complexity of HV-Rectilinear Planarity Testing. In, Christian Duncan, Antonios Symvonis, editors, Proc. 22nd International Symposium on Graph Drawing (GD '14), Springer-Verlag, volume 8871 of Lecture Notes in Computer Science, pages 343-354, 2014.

  2. Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani. On Embedding a Graph on the Grid with the Maximum Number of Bends and Other Bad Features. Theory of Computing Systems. 44(2):143-149. Feb 2009. Special Issue on Selected Papers from FUN '07. [conference version]

  3. Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani. On Embedding a Graph in the Grid with the Maximum Number of Bends and Other Bad Features (Invited Lecture). In, Pierluigi Crescenzi, Giuseppe Prencipe, Geppino Pucci, editors, Fun with Algorithms, 4th International Conference (FUN '07), Springer-Verlag, volume 4475 of Lecture Notes in Computer Science, pages 1-13, 2007. [journal version]

  4. Maurizio Patrignani. A Note on the Self-Similarity of Some Orthogonal Drawings. In 12th International Symposium on Graph Drawing (Proc. GD '04), Springer-Verlag, volume 3383 of Lecture Notes in Computer Science, pages 389-394, 2004. [ preliminary version]

  5. Walter Didimo, Maurizio Patrignani, Maurizio Pizzonia. Industrial Plant Drawer. In, P. Mutzel, M. Juenger, S. Leipert, editors, Graph Drawing (Proc. GD '01), Springer-Verlag, volume 2265 of Lecture Notes in Computer Science, pages 475-476, 2002. Software demo.

  6. Giuseppe Di Battista, Walter Didimo, Maurizio Patrignani, Maurizio Pizzonia. Drawing Database Schemas with DBDraw. In, P. Mutzel, M. Juenger, S. Leipert, editors, Graph Drawing (Proc. GD '01), Springer-Verlag, volume 2265 of Lecture Notes in Computer Science, pages 451-452, 2002. Software demo. [ preliminary version]

  7. Maurizio Patrignani. On the Complexity of Orthogonal Compaction. Computational Geometry: Theory and Applications. 19(1):47-67. 2001. [see TR] [conference version]

  8. Maurizio Patrignani. Visualization of Large Graphs. Doctoral Thesis. Universita' degli Studi di Roma ``La Sapienza'', Dottorato di Ricerca in Ingegneria Informatica, XIII Ciclo. 2001. [ download pdf]

  9. Maurizio Patrignani. Visualizzazione di Diagrammi in Tre Dimensioni. Universita' degli Studi di Roma ``La Sapienza'', Tesi di Laurea in Ingegneria Elettronica. 1996. (in Italian). [ download pdf]

  10. Maurizio Patrignani. On the Complexity of Orthogonal Compaction. In, F. Dehne, A. Gupta, J.-R. Sack, R. Tamassia, editors, 6th International Workshop Algorithms Data Struct. (Proc. WADS '99), Springer-Verlag, volume 1663 of Lecture Notes in Computer Science, pages 56-61, 1999. [ presentation at WADS 1999] [see TR] [journal version]

  11. Maurizio Patrignani. On the Complexity of Orthogonal Compaction. Technical Report RT-DIA-39-1999, Dip. Informatica e Automazione, Univ. Roma Tre, 1999. [conference version] [journal version]

  12. Giuseppe Di Battista, Walter Didimo, Maurizio Patrignani, Maurizio Pizzonia. Orthogonal and Quasi-Upward Drawings with Vertices of Prescribed Size. In, Jan Kratochv\'\il, editor, Graph Drawing (Proc. GD '99), Springer-Verlag, volume 1731 of Lecture Notes in Computer Science, pages 297-310, 1999. [ preliminary version]

3D Representations of Graphs

  1. Maurizio Patrignani. Complexity Results for Three-dimensional Orthogonal Graph Drawing. Journal of Discrete Algorithms. 6:140-161. 2008. [see TR] [conference version]

  2. Maurizio Patrignani. Complexity Results for Three-dimensional Orthogonal Graph Drawing. In, P. Healy, N.S. Nikolov, editors, 13th International Symposium on Graph Drawing (Proc. GD '05), Springer-Verlag, volume 3843 of Lecture Notes in Computer Science, pages 368-379, 2005. [ presentation at GD 2005] [see TR] [journal version]

  3. Maurizio Patrignani. Complexity Results for Three-dimensional Orthogonal Graph Drawing. Technical Report RT-DIA-94-2005, Dip. Informatica e Automazione, Univ. Roma Tre, 2005. [conference version] [journal version]

  4. Emilio Di Giacomo, Giuseppe Liotta, Maurizio Patrignani. A Note on 3D Orthogonal Drawings with Direction Constrained Edges. Information Processing Letters. 90:97-101. 2004.

  5. Emilio Di Giacomo, Giuseppe Liotta, Maurizio Patrignani. Orthogonal 3D Shapes of Theta Graphs. In, Michael Goodrich, Stephen Kobourov, editors, Graph Drawing (Proc. GD '02), Springer-Verlag, volume 2528 of Lecture Notes in Computer Science, pages 142-149, 2002. [ preliminary version] [ presentation at GD 2002]

  6. Emilio Di Giacomo, Giuseppe Liotta, Maurizio Patrignani. On Orthogonal 3D Shapes of Theta Graphs. Technical Report RT-DIA-71-2002, Dept. of Computer Sci., Univ. di Roma Tre, 2002.

  7. Maurizio Patrignani. Visualization of Large Graphs. Doctoral Thesis. Universita' degli Studi di Roma ``La Sapienza'', Dottorato di Ricerca in Ingegneria Informatica, XIII Ciclo. 2001. [ download pdf]

  8. Maurizio Patrignani. Visualizzazione di Diagrammi in Tre Dimensioni. Universita' degli Studi di Roma ``La Sapienza'', Tesi di Laurea in Ingegneria Elettronica. 1996. (in Italian). [ download pdf]

  9. Giuseppe Di Battista, Maurizio Patrignani, Francesco Vargiu. A Split-and-Push Approach to 3D Orthogonal Drawing. Journal of Graph Algorithms and Applications. 4(3):105-133. 2000. [conference version]

  10. Giuseppe Di Battista, Maurizio Patrignani, Francesco Vargiu. A Split-and-Push Approach to 3D Orthogonal Drawing. In, Sue Whitesides, editor, Graph Drawing (Proc. GD '98), Springer-Verlag, volume 1547 of Lecture Notes in Computer Science, pages 87-101, 1998. [journal version]

  11. Maurizio Patrignani, Francesco Vargiu. 3DCube: A Tool for Three Dimensional Graph Drawing. In, G. Di Battista, editor, Graph Drawing (Proc. GD '97), Springer-Verlag, volume 1353 of Lecture Notes in Computer Science, pages 284-290, 1998. [ preliminary version]

Clustered Planarity

  1. Patrizio Angelini, Giordano Da Lozzo, Marco Di Bartolomeo, Giuseppe Di Battista, Seok-Hee Hong, Maurizio Patrignani, Vincenzo Roselli. Anchored Drawings of Planar Graphs. In, Christian Duncan, Antonios Symvonis, editors, Proc. 22nd International Symposium on Graph Drawing (GD '14), Springer-Verlag, volume 8871 of Lecture Notes in Computer Science, pages 404-415, 2014. [ presentation at GD'14]

  2. Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, Vincenzo Roselli. Relaxing the Constraints of Clustered Planarity. Computational Geometry: Theory and Applications. 48(2):42-75. 2015.

  3. Patrizio Angelini, Giordano Da Lozzo and Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, Vincenzo Roselli. Relaxing the Constraints of Clustered Planarity . Technical Report arXiv:1207.3934, Cornell University, 2012.

  4. Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, Ignaz Rutter. Testing the Simultaneous Embeddability of Two Graphs whose Intersection is a Biconnected or a Connected Graph. Journal of Discrete Algorithms. 14:150-172. 2012.

Planarity and Planar Graphs

  1. Emilio Di Giacomo, Giuseppe Liotta, Maurizio Patrignani, Alessandra Tappini. NodeTrix Planarity Testing with Small Clusters. Technical Report arXiv:1708.09281, Cornell University, 2017.

  2. Tiziana Calamoneri, Valentino Di Donato, Diego Mariottini, Maurizio Patrignani. Visualizing Co-Phylogenetic Reconciliations. Technical Report arXiv:1708.09691, Cornell University, 2017.

  3. Steven Chaplick, Markus Chimani, Sabine Cornelsen, Giordano Da Lozzo, Martin Nöllenburg, Maurizio Patrignani, Ioannis G. Tollis, Alexander Wolff. Planar L-Drawings of Directed Graphs. Technical Report arXiv:1708.09107, Cornell University, 2017.

  4. Steven Chaplick, Markus Chimani, Sabine Cornelsen, Giordano Da Lozzo, Martin Nöllenburg, Maurizio Patrignani, Ioannis G. Tollis, Alexander Wolff. Planar L-Drawings of Directed Graphs. In Proc. 25th International Symposium on Graph Drawing and Network Visualization (GD '17), 2017. To Appear.

  5. Emilio Di Giacomo, Giuseppe Liotta, Maurizio Patrignani, Alessandra Tappini. NodeTrix Planarity Testing with Small Clusters. In Proc. 25th International Symposium on Graph Drawing and Network Visualization (GD '17), 2017. To Appear.

  6. Tiziana Calamoneri, Valentino Di Donato, Diego Mariottini, Maurizio Patrignani. Visualizing Co-Phylogenetic Reconciliations. In Proc. 25th International Symposium on Graph Drawing and Network Visualization (GD '17), 2017. To Appear.

  7. Tiziana Calamoneri, Valentino Di Donato, Diego Mariottini, Maurizio Patrignani. Visualizing Reconciliations in Co-Phylogeny (Extended Abstract). In 18th Italian Conference on Theoretical Computer Science (ICTCS 2017), 2017. To Appear.

  8. Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, Ignaz Rutter. Intersection-Link Representations of Graphs. Journal of Graph Algorithms and Applications. 21(4):731-755. 2017.

  9. Soroush Alamdari, Patrizio Angelini, Fidel Barrera-Cruz, Timothy M. Chan, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Penny Haxell, Anna Lubiw, Maurizio Patrignani, Vincenzo Roselli, Sahil Singla, Bryan T. Wilkinson. How to morph planar graph drawings. SIAM Journal on Computing. 46(2):824-852. 2017. [arXiv version]

  10. Fabrizio Frati, Maurizio Patrignani, Vincenzo Roselli. LR-Drawings of Ordered Rooted Binary Trees and Near-Linear Area Drawings of Outerplanar Graphs. In, Philip Klein, editor, Proc. 28th ACM-SIAM Symposium on Discrete Algorithms (SODA '17), ACM-SIAM, pages 1980-1999, 2017.

  11. Fabrizio Frati, Maurizio Patrignani, Vincenzo Roselli. LR-Drawings of Ordered Rooted Binary Trees and Near-Linear Area Drawings of Outerplanar Graphs. Technical Report arXiv:1610.02841, Cornell University, 2016.

  12. Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, Ignaz Rutter. Beyond Level Planarity. In, Martin Nöllenburg, Yifan Hu, editors, Proc. 24th International Symposium on Graph Drawing and Network Visualization (GD '16), Springer International Publishing, volume 9801 of Lecture Notes in Computer Science, pages 482-495, 2016.

  13. Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani. Computing NodeTrix Representations of Clustered Graphs. In, Martin Nöllenburg, Yifan Hu, editors, Proc. 24th International Symposium on Graph Drawing and Network Visualization (GD '16), Springer International Publishing, volume 9801 of Lecture Notes in Computer Science, pages 107-120, 2016.

  14. Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani. Computing NodeTrix Representations of Clustered Graphs. Technical Report arXiv:1608.08952, Cornell University, 2016.

  15. Soroush Alamdari, Patrizio Angelini, Fidel Barrera-Cruz, Timothy M. Chan, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Penny Haxell, Anna Lubiw, Maurizio Patrignani, Vincenzo Roselli, Sahil Singla, Bryan T. Wilkinson. How to morph planar graph drawings. Technical Report arXiv:1606.00425, Cornell University, 2016.

  16. Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, Ignaz Rutter. Beyond Level Planarity. Technical Report arXiv:1510.08274, Cornell University, 2015.

  17. Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, Ignaz Rutter. Intersection-Link Representations of Graphs. In, Emilio Di Giacomo, Anna Lubiw, editors, Proc. 23rd International Symposium on Graph Drawing and Network Visualization (GD '15), Springer-Verlag, volume 9411 of Lecture Notes in Computer Science, pages 217-230, 2015. [ presentation at GD'15]


  18. book coverPatrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, Ignaz Rutter
    On the Relationship between Map Graphs and Clique Planar Graphs
    In, Emilio Di Giacomo, Anna Lubiw, editors
    Proc. 23rd International Symposium on Graph Drawing and Network Visualization (GD '15)
    Springer-Verlag
    volume 9411 of Lecture Notes in Computer Science
    pages 548-550, 2015. Poster. [ presentation at GD'15] [best poster award at GD'15]

  19. Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, Ignaz Rutter. Intersection-Link Representations of Graphs. Technical Report arXiv:1508.07557, Cornell University, 2015.

  20. Patrizio Angelini, Giordano Da Lozzo, Marco Di Bartolomeo, Valentino Di Donato, Maurizio Patrignani, Vincenzo Roselli, Ioannis G. Tollis. L-Drawings of Directed Graphs. Technical Report arXiv:1509.00684, Cornell University, 2015.

  21. Carla Binucci, Emilio Di Giacomo, Walter Didimo, Fabrizio Montecchiani, Maurizio Patrignani, Antonios Symvonis, Ioannis G. Tollis. Fan-Planarity: Properties and Complexity. Theoretical Computer Science. 589:76-86. 2015.

  22. Patrizio Angelini, Giordano Da Lozzo, Fabrizio Frati, Anna Lubiw, Maurizio Patrignani, Vincenzo Roselli. Optimal Morphs of Convex Drawings. In, Lars Arge, J\'anos Pach, editors, Proc. 31st Symposium on Computational Geometry (SoCG '15), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, volume 34 of LIPIcs, pages 126-140, 2015.

  23. Patrizio Angelini, Giordano Da Lozzo, Fabrizio Frati, Anna Lubiw, Maurizio Patrignani and Vincenzo Roselli. Optimal Morphs of Convex Drawings. Technical Report arXiv:1503.09021, Cornell University, 2015.

  24. Patrizio Angelini, Giordano Da Lozzo, Marco Di Bartolomeo, Giuseppe Di Battista, Seok-Hee Hong, Maurizio Patrignani, Vincenzo Roselli. Anchored Drawings of Planar Graphs. In, Christian Duncan, Antonios Symvonis, editors, Proc. 22nd International Symposium on Graph Drawing (GD '14), Springer-Verlag, volume 8871 of Lecture Notes in Computer Science, pages 404-415, 2014. [ presentation at GD'14]

  25. Walter Didimo, Giuseppe Liotta, Maurizio Patrignani. On the Complexity of HV-Rectilinear Planarity Testing. In, Christian Duncan, Antonios Symvonis, editors, Proc. 22nd International Symposium on Graph Drawing (GD '14), Springer-Verlag, volume 8871 of Lecture Notes in Computer Science, pages 343-354, 2014.

  26. Carla Binucci, Emilio Di Giacomo, Walter Didimo, Fabrizio Montecchiani, Maurizio Patrignani, Ioannis G. Tollis. Fan-planar Graphs: Combinatorial Properties and Complexity Results. In, Christian Duncan, Antonios Symvonis, editors, Proc. 22nd International Symposium on Graph Drawing (GD '14), Springer-Verlag, volume 8871 of Lecture Notes in Computer Science, pages 186-197, 2014.

  27. Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, Vincenzo Roselli. Relaxing the Constraints of Clustered Planarity. Computational Geometry: Theory and Applications. 48(2):42-75. 2015.

  28. Carla Binucci, Emilio Di Giacomo, Walter Didimo, Fabrizio Montecchiani, Maurizio Patrignani, Ioannis G. Tollis. Properties and Complexity of Fan-Planarity. Technical Report arXiv:1406.5299, Cornell University, 2014.

  29. Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, Vìt Jelìnek, Jan Kratochvìl, Maurizio Patrignani, Ignaz Rutter. Testing Planarity of Partially Embedded Graphs. ACM Transactions on Algorithms. 11(4). 2015. Article No. 32.

  30. Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani and Vincenzo Roselli. Morphing Planar Graph Drawings Optimally. In Proc. 41st International Colloquium on Automata, Languages and Programming (ICALP '14), Springer Verlag, volume 8572 of Lecture Notes in Computer Science, pages 126-137, 2014.

  31. Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani and Vincenzo Roselli. Morphing Planar Graph Drawings Optimally. Technical Report arXiv:1402.4364, Cornell University, 2014.

  32. Carla Binucci, Walter Didimo, Maurizio Patrignani. Upward and Quasi-Upward Planarity Testing of Embedded Mixed Graphs. Theor. Computer Science. 526:75-89. 2014.

  33. Patrizio Angelini, Carla Binucci, Giordano Da Lozzo, Walter Didimo, Luca Grilli, Fabrizio Montecchiani and Maurizio Patrignani, Ioannis Tollis. Algorithms and Bounds for Drawing Non-planar Graphs with Crossing-free Subgraphs. Technical Report arXiv:1308.6706, Cornell University, 2013.

  34. Patrizio Angelini, Pier Francesco Cortese, Giuseppe Di Battista, Maurizio Patrignani. Topological Morphing of Planar Graphs. Theor. Computer Science. 514:2-20. 2013.

  35. Patrizio Angelini, Carla Binucci, Giordano Da Lozzo, Walter Didimo, Luca Grilli, Fabrizio Montecchiani, Maurizio Patrignani, Ioannis Tollis. Drawing Non-planar Graphs with Crossing-free Subgraphs. In, Stephen Wismath, Alexander Wolff, editors, Proc. 21st International Symposium on Graph Drawing (GD '13), Springer-Verlag, volume 8242 of Lecture Notes in Computer Science, pages 295-307, 2013. [ presentation at GD'13]

  36. Patrizio Angelini, Fabrizio Frati, Maurizio Patrignani, Vincenzo Roselli. Morphing Planar Graph Drawings Efficiently. In, Stephen Wismath, Alexander Wolff, editors, Proc. 21st International Symposium on Graph Drawing (GD '13), Springer-Verlag, volume 8242 of Lecture Notes in Computer Science, pages 49-60, 2013. [ presentation at GD'13]

  37. Patrizio Angelini, Fabrizio Frati, Maurizio Patrignani, Vincenzo Roselli. Morphing Planar Graph Drawings Efficiently. Technical Report arXiv:1308.4291, Cornell University, 2013.

  38. Soroush Alamdari, Patrizio Angelini, Timothy M. Chan, Giuseppe Di Battista, Fabrizio Frati, Anna Lubiw, Maurizio Patrignani, Vincenzo Roselli, Sahil Singla, Bryan T. Wilkinson. Morphing Planar Graph Drawings with a Polynomial Number of Steps. In 24th ACM-SIAM Symposium on Discrete Algorithms (SODA '13), pages 1656-1667, 2013. [ presentation at SODA'13]

  39. Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani. Nonconvex Representations of Plane Graphs. SIAM Journal on Discrete Mathematics. 26(4):1670-1681. 2012.


  40. book coverMaurizio Patrignani
    Planarity Testing and Embedding
    In, Roberto Tamassia, editor
    Handbook of Graph Drawing and Visualization, Discrete Mathematics and Its Applications
    Chapman and Hall/CRC Press
    pages 1-42, 2013.

  41. Patrizio Angelini, Enrico Colasante, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani. Monotone Drawings of Graphs. Journal of Graph Algorithms and Applications. 16(1):5-35. 2012. Special Issue on Selected Papers from GD '10. [ download pdf]

  42. Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, Ignaz Rutter. Testing the Simultaneous Embeddability of Two Graphs whose Intersection is a Biconnected or a Connected Graph. Journal of Discrete Algorithms. 14:150-172. 2012.

  43. Carla Binucci, Walter Didimo, Maurizio Patrignani. Upward and Quasi-Upward Planarity Testing of Embedded Mixed Graphs. Technical Report RT 001-12, Dipartimento di Ingegneria Elettronica e dell'Informazione, Perugia University, 2012.

  44. Maurizio Patrignani. Finding Bimodal and Acyclic Orientations of Mixed Planar Graphs is NP-Complete. Technical Report RT-DIA-188-2011, Dept. of Computer Science and Automation, Roma Tre University, 2011.

  45. Vladimir Batagelj, Franz J. Brandenburg, Walter Didimo, Giuseppe Liotta, Pietro Palladino, Maurizio Patrignani. Visual Analysis of Large Graphs Using $(X,Y)$-clustering and Hybrid Visualizations. IEEE Transactions on Visualization and Computer Graphics. 17(11):1587-1598. 2011.

  46. Patrizio Angelini, Enrico Colasante, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani. Monotone Drawings of Graphs. In, U. Brandes, S. Cornelsen, editors, 18th International Symposium on Graph Drawing (GD '10), Springer-Verlag, volume 6502 of Lecture Notes in Computer Science, pages 13-24, 2011. [ Slides (PPT)]

  47. Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, Ignaz Rutter. Testing the Simultaneous Embeddability of Two Graphs whose Intersection is a Biconnected Graph or a Tree. In Workshop on Combinatorial Algorithms (IWOCA '10), Springer-Verlag, volume 6460 of Lecture Notes in Computer Science, pages 212-225, 2011.

  48. Patrizio Angelini, Enrico Colasante, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani. Monotone Drawings of Graphs. Technical Report RT-DIA-178-2010, Dept. of Computer Science and Automation, Roma Tre University, 2010.

  49. Patrizio Angelini, Giuseppe Di Battista, Maurizio Patrignani. Finding a Minimum-Depth Embedding of a Planar Graph in O(n^4) Time. Algorithmica. 60(4):890-937. 2011.

  50. Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, Vìt Jelìnek, Jan Kratochvìl, Maurizio Patrignani, Ignaz Rutter. Testing Planarity of Partially Embedded Graphs. In, M. Charikar, editor, Symposium On Discrete Algorithms (SODA '10), ACM-SIAM, pages 202-221, 2010.

  51. Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani. Non-convex Representations of Graphs. Technical Report RT-DIA-135-2008, Dept. of Computer Science and Automation, Roma Tre University, 2008. [conference version]

  52. Patrizio Angelini, Pier Francesco Cortese, Giuseppe Di Battista, Maurizio Patrignani. Topological Morphing of Planar Graphs. Technical Report RT-DIA-134-2008, Dept. of Computer Science and Automation, Roma Tre University, 2008. [conference version]

  53. Patrizio Angelini, Pier Francesco Cortese, Giuseppe Di Battista, Maurizio Patrignani. Topological Morphing of Planar Graphs. In, Ioannis G. Tollis, Maurizio Patrignani, editors, 16th International Symposium on Graph Drawing (GD '08), Springer-Verlag, volume 5417 of Lecture Notes in Computer Science, pages 145-156, 2009. [see TR]

  54. Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani. Non-Convex Representations of Graphs. In, I. G. Tollis, M. Patrignani, editors, 16th International Symposium on Graph Drawing (GD '08), Springer-Verlag, volume 5417 of Lecture Notes in Computer Science, pages 390-395, 2009. [see TR]

  55. Melanie Badent, Carla Binucci, Emilio Di Giacomo, Walter Didimo, Stefan Felsner, Francesco Giordano, Jan Kratochvìl, Pietro Palladino, Maurizio Patrignani, Francesco Trotta. Homothetic Triangle Contact Representations of Planar Graphs. In, Prosenjit Bose, editor, 19th Canadian Conference on Computational Geometry (CCCG '07), pages 233-236, 2007.

  56. Fabrizio Frati, Maurizio Patrignani. A Note on Minimum Area Straight-line Drawings of Planar Graphs. In, Seok-Hee Hong, Takao Nishizeki, editors, 15th International Symposium on Graph Drawing (GD '07), Springer-Verlag, volume 4875 of Lecture Notes in Computer Science, pages 339-344, 2007.

  57. Patrizio Angelini, Giuseppe Di Battista, Maurizio Patrignani. Computing a Minimum-Depth Planar Graph Embedding in O(n^4) Time. In, Frank Dehne, Joerg-Ruediger Sack, Norbert Zeh, editors, 10th Workshop on Algorithms and Data Structures (WADS '07), Springer-Verlag, volume 4619 of Lecture Notes in Computer Science, pages 287-299, 2007. [see TR]

  58. Patrizio Angelini, Giuseppe Di Battista, Maurizio Patrignani. Computing a Minimum-Depth Planar Graph Embedding in O(n^4) Time. Technical Report RT-DIA-116-2007, Dept. of Computer Science and Automation, University of Roma Tre, 2007. [conference version]

  59. Maurizio Patrignani. On Extending a Partial Straight-Line Drawing. International Journal of Foundations of Computer Science (IJFCS), Special Issue on Graph Drawing. 17(5):1061-1069. 2006. [see TR] [conference version]

  60. Pier Francesco Cortese, Giuseppe Di Battista, Fabrizio Frati, Luca Grilli, Katharina Anna Lehmann, Giuseppe Liotta, Maurizio Patrignani, Ioannis Tollis, Francesco Trotta. On the Topologies of Local Minimum Spanning Trees. In, Thomas Erlebach, editor, 3rd Workshop on Combinatorial and Algorithmic Aspects of the Networks (CAAN '06), Springer-Verlag, volume 4235 of Lecture Notes in Computer Science, pages 31-44, 2006. [see TR]

  61. Pier Francesco Cortese, Giuseppe Di Battista, Fabrizio Frati, Luca Grilli, Katharina Anna Lehmann, Giuseppe Liotta, Maurizio Patrignani, Ioannis Tollis, Francesco Trotta. On the Topologies of Local Minimum Spanning Trees. Technical Report RT-001-06, Dip. Ingegneria Elettronica e dell'Informazione, Univ. Perugia, 2006. [conference version]

  62. Maurizio Patrignani. On Extending a Partial Straight-Line Drawing. In, P. Healy, N.S. Nikolov, editors, 13th International Symposium on Graph Drawing (Proc. GD '05), Springer-Verlag, volume 3843 of Lecture Notes in Computer Science, pages 380-385, 2005. [ presentation at GD 2005] [see TR] [journal version]

  63. Maurizio Patrignani. On Extending a Partial Straight-Line Drawing. Technical Report RT-DIA-99-2005, Dip. Informatica e Automazione, Univ. Roma Tre, 2005. [conference version] [journal version]

  64. John Michael Boyer, Pier Francesco Cortese, Maurizio Patrignani, Giuseppe Di Battista. Stop Minding Your P's and Q's: Implementing a Fast and Simple DFS-based Planarity Testing and Embedding Algorithm. In, Giuseppe Liotta, editor, Graph Drawing (Proc. GD '03), Springer-Verlag, volume 2912 of Lecture Notes in Computer Science, pages 25-36, 2004. [see TR]

  65. John Michael Boyer, Pier Francesco Cortese, Maurizio Patrignani, Giuseppe Di Battista. Stop Minding Your P's and Q's: Implementing a Fast and Simple DFS-based Planarity Testing and Embedding Algorithm. Technical Report RT-DIA-83-2003, Dip. Informatica e Automazione, Univ. Roma Tre, 2003. [conference version]

Minimum Size Representations of Graphs

  1. Fabrizio Frati, Maurizio Patrignani, Vincenzo Roselli. LR-Drawings of Ordered Rooted Binary Trees and Near-Linear Area Drawings of Outerplanar Graphs. In, Philip Klein, editor, Proc. 28th ACM-SIAM Symposium on Discrete Algorithms (SODA '17), ACM-SIAM, pages 1980-1999, 2017.

  2. Patrizio Angelini, Enrico Colasante, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani. Monotone Drawings of Graphs. In, U. Brandes, S. Cornelsen, editors, 18th International Symposium on Graph Drawing (GD '10), Springer-Verlag, volume 6502 of Lecture Notes in Computer Science, pages 13-24, 2011. [ Slides (PPT)]

  3. Fabrizio Frati, Maurizio Patrignani. A Note on Minimum Area Straight-line Drawings of Planar Graphs. In, Seok-Hee Hong, Takao Nishizeki, editors, 15th International Symposium on Graph Drawing (GD '07), Springer-Verlag, volume 4875 of Lecture Notes in Computer Science, pages 339-344, 2007.

Simultaneous Information Visualization

  1. Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, Ignaz Rutter. Beyond Level Planarity. Technical Report arXiv:1510.08274, Cornell University, 2015.

  2. Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, Ignaz Rutter. Testing the Simultaneous Embeddability of Two Graphs whose Intersection is a Biconnected or a Connected Graph. Journal of Discrete Algorithms. 14:150-172. 2012.

  3. Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, Ignaz Rutter. Testing the Simultaneous Embeddability of Two Graphs whose Intersection is a Biconnected Graph or a Tree. In Workshop on Combinatorial Algorithms (IWOCA '10), Springer-Verlag, volume 6460 of Lecture Notes in Computer Science, pages 212-225, 2011.

Dynamic Graph Drawing

  1. Camil Demetrescu, Giuseppe Di Battista, Irene Finocchi, Giuseppe Liotta, Maurizio Patrignani and Maurizio Pizzonia. Infinite Trees and the Future. In, Jan Kratochv\'\il, editor, Graph Drawing (Proc. GD '99), Springer-Verlag, volume 1731 of Lecture Notes in Computer Science, pages 379-391, 1999. [ preliminary version]

Discovery and Analysis of Interdomain Routing Policies

  1. Lorenzo Colitti, Giuseppe Di Battista, Maurizio Patrignani, Maurizio Pizzonia, Massimo Rimondini. Investigating Prefix Propagation through Active BGP Probing. Microprocessors and Microsystems. 31:460-474. 2007. [see TR] [conference version]

  2. Lorenzo Colitti, Giuseppe Di Battista, Maurizio Patrignani, Maurizio Pizzonia, Massimo Rimondini. Investigating Prefix Propagation through Active BGP Probing. In, Paolo Bellavista, Chi-Ming Chen, editors, 11th IEEE Symposium on Computers and Communications (ISCC 2006), IEEE Computer Society, pages 497-504, 2006. [see TR] [journal version]

  3. Lorenzo Colitti, Giuseppe Di Battista, Maurizio Patrignani, Maurizio Pizzonia, Massimo Rimondini. Active BGP Probing. Technical Report RT-DIA-102-2005, Dip. Informatica e Automazione, Univ. Roma Tre, 2005. [conference version] [journal version]

Inference of commercial relationships between Internet Service Providers.

  1. Giuseppe Di Battista, Thomas Erlebach, Alexander Hall, Maurizio Patrignani, Maurizio Pizzonia, Thomas Schank. Computing the Types of the Relationships between Autonomous Systems. IEEE/ACM Transactions on Networking. 15(2):267-280. Apr 2007.

  2. Pier Francesco Cortese, Giuseppe Di Battista, Antonello Moneta, Maurizio Patrignani, Maurizio Pizzonia. Topographic Visualization of Prefix Propagation in the Internet. IEEE Transactions on Visualization and Computer Graphics. 12(5):725-732. 2006. [see TR]

  3. Pier Francesco Cortese, Giuseppe Di Battista, Antonello Moneta, Maurizio Patrignani, Maurizio Pizzonia. Topographic Visualization of the Internet. Technical Report RT-DIA-104-2005, Dip. Informatica e Automazione, Univ. Roma Tre, 2005. [journal version]

  4. Massimo Rimondini, Maurizio Pizzonia, Giuseppe Di Battista, Maurizio Patrignani. Algorithms for the Inference of the Commercial Relationships between Autonomous Systems: Results Analysis and Model Validation. In 2nd International Workshop on Inter-Domain Performance and Simulation (IPS 2004), pages 33-45, 2004. [ presentation at IPS 2004]

  5. Marco Gaertler, Maurizio Patrignani. Dynamic Analysis of the Autonomous System Graph. In 2nd International Workshop on Inter-Domain Performance and Simulation (IPS 2004), pages 13-24, 2004.

  6. Giuseppe Di Battista, Federico Mariani, Maurizio Patrignani, Maurizio Pizzonia. BGPlay: a System for Visualizing the Interdomain Routing Evolution. In, Giuseppe Liotta, editor, Graph Drawing (Proc. GD '03), Springer-Verlag, volume 2912 of Lecture Notes in Computer Science, pages 295-306, 2004. [journal version]

  7. Giuseppe Di Battista, Maurizio Patrignani, Maurizio Pizzonia. Computing the Types of the Relationships between Autonomous Systems. In IEEE INFOCOM 2003, pages 156-165, 2003. [ presentation at INFOCOM 2003] [see TR]

  8. Giuseppe Di Battista, Federico Mariani, Maurizio Patrignani, Maurizio Pizzonia. Archives of BGP Updates: Integration and Visualization. In Proceedings of IPS 2003, International Workshop on Inter-domain Performance and Simulation, pages 123-129, 2003. [ preliminary version]

  9. Giuseppe Di Battista, Maurizio Patrignani, Maurizio Pizzonia. Computing the Types of Relationships between Autonomous Systems. Technical Report RT-DIA-73-2002, Dip. Informatica e Automazione, Univ. Roma Tre, 2002. [conference version]

IPv6 Tunnel Discovery

  1. Lorenzo Colitti, Giuseppe Di Battista, Maurizio Patrignani. IPv6-in-IPv4 tunnel discovery: methods and experimental results. IEEE Transactions on Network and Service Management. 1(1):2-10. Apr 2004. [see TR] [conference version]

  2. Lorenzo Colitti, Giuseppe Di Battista, Maurizio Patrignani. Discovering IPv6-in-IPv4 Tunnels in the Internet. In, R. Boutaba, S.-B. Kim, editors, Proc. IEEE/IFIP Network Operations and Management Symposium (NOMS 2004), pages 613-626, 2004. [ preliminary version] [see TR] [journal version]

  3. Lorenzo Colitti, Giuseppe Di Battista, Maurizio Patrignani. Discovering IPv6-in-IPv4 Tunnels in the Internet. Technical Report RT-DIA-82-2003, Dip. Informatica e Automazione, Univ. Roma Tre, 2003. [conference version] [journal version]