Universität Tübingen Fakultät > Wilhelm-Schickard-Institut > Algorithmik > Lehrstuhl > Mitarbeiter > Patrizio Angelini
Arbeitsbereich Algorithmik

Dr. Patrizio Angelini

Address

Arbeitsbereich Algorithmik
Wilhelm-Schickard Institut für Informatik
Sand 14, D-72076 Tübingen, Deutschland







Contact Information

Email:angelini[nospam_AT]informatik[dot]uni[dash]tuebingen[dot]de
Phone:+49-7071-2970478
Room:C106
Office hours:by appointment


Education | Research Interests | Teaching | Publications | Participation to PC

Education

    Ph.D. in Computer Science
    30/03/2010, Roma Tre University, Rome
    Advisor: Prof. Giuseppe Di Battista
    Thesis: On the existence and optimality of some planar graph embeddings
    Master Degree in Computer Engineering, 110 cum laude
    30/03/2006, Roma Tre University, Rome

Research Interests

    My research interest is on Algorithms and Complexity for graph problems. In particular, my main focus is on problems concerning the visualization of graphs (Graph Drawing).
    The theoretical aspect of these problems spans the research fields of Computational Geometry, Graph Theory, and Discrete Mathematics.
    On the other hand, the problems I study have a strong applicative flavour, as they are strictly related to the Information Visualization field, and in particular to the Network Visualization one.

Teaching

Universität Tübingen
    Dozent (Main teacher): Spezielle Themen der Algorithmik (SS 15/16 - SS 16/17)
    Übungen zur Vorlesung (Assistant): Algorithmen und Komplexität (WS 15/16 - WS 16/17)
    Seminar (Student supervisor): Kombinatorische Algorithmen (WS 15/16)
    Seminar (Student supervisor): Beyond Planarity (WS 16/17)

Roma Tre University
    Dozent (Main Teacher): Algorithmic Techniques for Graphs and Networks (10/11)
    Übungen zur Vorlesung (Assistant): Algorithmic Techniques for Graphs and Networks (09/10)
    Übungen zur Vorlesung (Assistant): Theoretical Computer Science (from 06/07 to 14/15)
    Seminar (Student supervisor): Information Visualization (13/14 and 14/15)

Publications

International Journals

  1. S. Alamdari, P. Angelini, F. Barrera-Cruz, T. M. Chan, G. Da Lozzo, G. Di Battista, F. Frati, P. Haxell, A. Lubiw, M. Patrignani, V. Roselli, S. Singla, B. T. Wilkinson (2017) How to morph planar graph drawings. SIAM Journal on Computing. To appear

  2. P. Angelini (2017) Monotone Drawings of Graphs with Few Directions. Information Processing Letters. Article in press. DOI: 10.1016/j.ipl.2016.12.004

  3. P. Angelini, G. Da Lozzo, G. Di Battista, F. Frati (2016) Strip Planarity Testing for Embedded Planar Graphs. Algorithmica. Article in press. DOI: 10.1007/s00453-016-0128-9

  4. P. Angelini, G. Da Lozzo (2017) SEFE = C-Planarity?. The Computer Journal 59(12):1831-1838.

  5. P. Angelini, W.S. Evans, F. Frati, J. Gudmundsson (2016) SEFE without Mapping via Large Induced Outerplane Graphs in Plane Graphs. Journal of Graph Theory 82(1): 45-64.

  6. P. Angelini, C. Binucci, G. Da Lozzo, W. Didimo, L. Grilli, F. Montecchiani, M. Patrignani, I. Tollis (2015) Algorithms and Bounds for Drawing Non-planar Graphs with Crossing-free Subgraphs. Computational Geometry: Theory and Applications 50(1): 34-48.

  7. P. Angelini, W. Didimo, S.G. Kobourov, T. Mchedlidze, V. Roselli, A. Symvonis, S.K. Wismath (2015) Monotone Drawings of Graphs with Fixed Embedding. Algorithmica 71(2): 233-257.

  8. P. Angelini, G. Da Lozzo, D. Neuwirth (2015) Advancements on SEFE and Partitioned Book Embedding problems. Theoretical Computer Science 575: 71-89.

  9. P. Angelini, G. Da Lozzo, G. Di Battista, F. Frati, V. Roselli (2015) The importance of being proper: (In clustered-level planarity and T-level planarity). Theoretical Computer Science 571: 1-9.

  10. P. Angelini, G. Di Battista, F. Frati, V. Jelinek, J. Kratochvil, M. Patrignani, I. Rutter (2015). Testing Planarity of Partially Embedded Graphs. ACM Trans. Algorithms 11(4): 32.

  11. P. Angelini, G. Da Lozzo, G. Di Battista, F. Frati, M. Patrignani, V. Roselli (2015) Relaxing the Constraints of Clustered Planarity. Computational Geometry: Theory and Applications, 48:42-75.

  12. P. Angelini, T. Blaesius, I. Rutter (2014) Testing Mutual duality of Planar graphs. International Journal on Computational Geometry and Applications 24(4): 325-346.

  13. P. Angelini, D. Eppstein, F. Frati, M. Kaufmann, S. Lazard, T. Mchedlidze, M. Teillaud, A. Wolff (2014) Universal Point Sets for Planar Graph Drawings with Circular Arcs. Journal of Graph Algorithms and Applications 18(3):313-324.

  14. P. Angelini, T. Bruckdorfer, M. Chiesa, F. Frati, M. Kaufmann, C. Squarcella (2014) On the Area Requirements of Euclidean Minimum Spanning Trees. Computational Geometry: Theory and Applications 47(2):200-213.

  15. P. Angelini, P.F. Cortese, G. Di Battista, M. Patrignani (2013) Topological Morphing of Planar Graphs. Theoretical Computer Science 514:2-20.

  16. P. Angelini, G. Di Battista, F. Frati (2013) Simultaneous Embedding of Embedded Planar Graphs. International Journal on Computational Geometry and Applications. 23(2):93-126.

  17. P. Angelini, E. Colasante, G. Di Battista, F. Frati, M. Patrignani (2012) Monotone Drawings of Graphs. Journal of Graph Algorithms and Applications. 16(1):5-35.

  18. P. Angelini, M. Geyer, M. Kaufmann, D. Neuwirth (2012) On a Tree and a Path with no Geometric Simultaneous Embedding. Journal of Graph Algorithms and Applications. 16(1):37-83.

  19. P. Angelini, G. Di Battista, F. Frati, M. Patrignani, I. Rutter (2012) Testing the Simultaneous Embeddability of Two Graphs whose Intersection is a Biconnected or a Connected Graph. Journal of Discrete Algorithms. 14:150-172.

  20. P. Angelini, G. Di Battista, F. Frati (2012) Succinct Greedy Drawings Do Not Always Exist. Networks 59(3):267-274.

  21. P. Angelini, F. Frati (2012) Acyclically 3-Colorable Planar Graphs. Journal of Combinatorial Optimization 24(2):116-130.

  22. P. Angelini, F. Frati, M. Kaufmann (2011) Straight-line Rectangular Drawings of Clustered Graphs. Discrete and Computational Geometry 45(1):88-140.

  23. P. Angelini, L. Cittadini, G. Di Battista, W. Didimo, F. Frati, M. Kaufmann, A. Symvonis (2011) On the Perspectives Opened by Right Angle Crossing Drawings. Journal of Graph Algorithms and Applications 15(1):53-78.

  24. P. Angelini, G. Di Battista, M. Patrignani (2011) Finding a Minimum-Depth Embedding of a Planar Graph in O(n^4) Time. Algorithmica 60(4):890-937.

  25. P. Angelini, F. Frati, L. Grilli (2010) An Algorithm to Construct Greedy Drawings of Triangulations. Journal of Graph Algorithms and Applications 14(1):19-51.

Proceedings of International Conferences

  1. P. Angelini, G. Da Lozzo (2016) Clustered Planarity with Pipes. In: S.-H.Hong, P.Eades, A.Meidiana, eds., 27th International Symposium on Algorithms and Computation (ISAAC '16), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, vol. 64 of LIPIcs, pp. 13:1-13:13.

  2. P. Angelini, M.A. Bekos, T. Bruckdorfer, J. Hancl, M. Kaufmann, S. Kobourov, J. Kratochvil, A. Symvonis, P. Valtr (2016) Low Ply Drawings of Trees. In: M.Noellenburg, Y.Hu, eds., 24th International Symposium on Graph Drawing and Network Visualization (GD '16), Springer, vol. 9801 of LNCS, pp. 236-248.

  3. P. Angelini, G. Da Lozzo, G. Di Battista, F. Frati, M. Patrignani, I. Rutter (2016) Beyond Level Planarity. In: M.Noellenburg, Y.Hu, eds., 24th International Symposium on Graph Drawing and Network Visualization (GD '16), Springer, vol. 9801 of LNCS, pp. 482-495.

  4. P. Angelini, S. Chaplick, S. Cornelsen, G. Da Lozzo, G. Di Battista, P. Eades, P. Kindermann, J. Kratochvil, F. Lipp, I. Rutter (2016) Simultaneous Orthogonal Planarity. In: M.Noellenburg, Y.Hu, eds., 24th International Symposium on Graph Drawing and Network Visualization (GD '16), Springer, vol. 9801 of LNCS, pp. 532-545.

  5. P. Angelini, G. Da Lozzo, G. Di Battista, V. Di Donato, P. Kindermann, G. Rote, I. Rutter (2016) Windrose Planarity: Embedding Graphs with Direction-Constrained Edges. In: R.Krauthgamer, ed., 27th Symposium on Discrete Algorithms (SODA '16), ACM-SIAM, pp. 985-996.

  6. P. Angelini (2016) Monotone drawings of graphs with few directions. In: N.G.Bourbakis, G.A.Tsihrintzis, M.Virvou, eds., 6th International Conference on Information, Intelligence, Systems and Applications (IISA 2015), IEEE, pp. 1-6, DOI: 10.1109/IISA.2015.7388003.

  7. P. Angelini, G. Da Lozzo, M. Di Bartolomeo, V. Di Donato, M. Patrignani, V. Roselli, I.G. Tollis (2016) L-Drawings of Directed Graphs. In: R.M.Freivalds, G.Engels, B.Catania, eds., 42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM '16), Springer, vol. 9587 of LNCS, pp. 134-147. Received the Best Paper Award.

  8. P. Angelini, M.A. Bekos, M. Kaufmann, V. Roselli (2016) Vertex-Coloring with Star-Defects. In: M. Kaykobad, R. Petreschi, eds., 10th International Workshop on Algorithms and Computation (WALCOM '16), Springer, vol. 9627 of LNCS, pp. 40-51.

  9. P. Angelini, G. Da Lozzo, F. Frati, A. Lubiw, M. Patrignani, V. Roselli (2015) Optimal Morphs of Convex Drawings. In: L.Arge, J.Pach, eds., 31st International Symposium on Computational Geometry (SoCG '15), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, vol. 34 of LIPIcs, pp. 126-140.

  10. P. Angelini, T. Bruckdorfer, M. Kaufmann, T. Mchedlidze (2015) A Universal Point Set for 2-Outerplanar Graphs. In: E. Di Giacomo, A. Lubiw, eds., 23rd International Symposium on Graph Drawing (GD '15), Springer, vol. 9411 of LNCS, pp. 409-422.

  11. P. Angelini, G. Da Lozzo, G. Di Battista, F. Frati, M. Patrignani, I. Rutter (2015) Intersection-Link Representations of Graphs. In: E. Di Giacomo, A. Lubiw, eds., 23rd International Symposium on Graph Drawing (GD '15), Springer, vol. 9411 of LNCS, pp. 217-230.

  12. P. Angelini, G. Da Lozzo, G. Di Battista, F. Frati, M. Patrignani, V. Roselli (2014)Morphing Planar Graph Drawings Optimally. In: J. Esparza, P. Fraigniaud, T. Husfeldt, E. Koutsoupias, eds., 41st International Colloquium on Automata, Languages and Programming (ICALP '14), Part I, Springer, vol. 8572 of LNCS, pp. 126-137.

  13. P. Angelini, G. Da Lozzo, D. Neuwirth (2014) On some NP-complete SEFE Problems. In: S. Pal, K. Sadakane, eds., Workshop on Algorithms and Computation (WALCOM'14), Springer, vol. 8344 of LNCS, pp. 193-205.

  14. P. Angelini, G. Da Lozzo, G. Di Battista, F. Frati, V. Roselli (2014) The Importance of Being Proper (In Clustered-Level Planarity and T-Level Planarity). In: C.A.Duncan, A.Symvonis, eds., 22nd International Symposium on Graph Drawing (GD '14), Springer, vol. 8871 of LNCS, pp. 246-258.

  15. P. Angelini, G. Da Lozzo, M. Di Bartolomeo, G. Di Battista, S.-H. Hong, M. Patrignani, V. Roselli (2014) Anchored Drawings of Planar Graphs. In: C.A.Duncan, A.Symvonis, eds., 22nd International Symposium on Graph Drawing (GD '14), Springer, vol. 8871 of LNCS, pp. 404-415.

  16. P. Angelini, T. Blaesius, I. Rutter (2014) Testing Mutual Duality of Planar Graphs. In: L.Cai, S.Cheng, T.Lam, eds., 24th International Symposium on Algorithms and Computation (ISAAC 2013), Springer, vol. 8283 of LNCS, pp. 350-360.

  17. P. Angelini, W. Evans, F. Frati, J. Gudmundsson (2013) SEFE with No Mapping via Large Induced Outerplane Graphs in Plane Graphs. In: L. Cai, S. Cheng, T. Lam, eds., 24th International Symposium on Algorithms and Computation (ISAAC 2013), Springer, vol. 8283 of LNCS, pp. 185-195.

  18. P. Angelini, G. Da Lozzo, G. Di Battista, F. Frati (2013) Strip Planarity Testing. In: S.Wismath, A.Wolff, eds., 21st International Symposium on Graph Drawing (GD '13), Springer, vol. 8242 of LNCS, pp. 37-48.

  19. P. Angelini, F. Frati, M. Patrignani, V. Roselli (2013) Morphing Planar Graph Drawings Efficiently. In: S.Wismath, A.Wolff, eds., 21st International Symposium on Graph Drawing (GD '13), Springer, vol. 8242 of LNCS, pp. 49-60.

  20. P. Angelini, C. Binucci, G. Da Lozzo, W. Didimo, L. Grilli, F. Montecchiani, M. Patrignani, I. Tollis (2013) Drawing Non-planar Graphs with Crossing-free Subgraphs. In: S.Wismath, A.Wolff, eds., 21st International Symposium on Graph Drawing (GD '13), Springer, vol. 8242 of LNCS, pp. 295-307.

  21. S. Alamdari, P. Angelini, T.M. Chan, G. Di Battista, F. Frati, A. Lubiw, M. Patrignani, V. Roselli, S. Singla, B.T. Wilkinson (2013) Morphing Planar Graph Drawings with a Polynomial Number of Steps. In: S. Khanna, ed., 24th Symposium on Discrete Algorithms (SODA '13), ACM-SIAM, pp. 1656-1667.

  22. P. Angelini, M. Di Bartolomeo, G. Di Battista (2013) Implementing a Partitioned 2-Page Book Embedding Algorithm. In: W.Didimo and M.Patrignani, eds., 20th International Symposium on Graph Drawing (GD '12), Springer, vol. 7704 of LNCS, pp. 79-89.

  23. P. Angelini, C. Binucci, W. Evans, F. Hurtado, G. Liotta, T. Mchedlidze, H. Meijer, Y. Okamoto (2012) Universal Point Subsets for Planar Graphs. In: K.-M.Chao, T.-S.Hsu, D.-T.Lee, eds., 23rd International Symposium on Algorithms and Computation (ISAAC 2012), Springer, vol. 7676 of LNCS, pp. 423-432.

  24. P. Angelini, G. Di Battista, W. Didimo, F. Frati, S.-H. Hong, M. Kaufmann, G. Liotta, A. Lubiw (2012) Large angle crossing drawings of planar graphs in subquadratic area. In: Special Festschrift volume in honor of Prof. F. Hurtado, vol. 7579 of LNCS, pp. 200-209.

  25. P. Angelini, G. Di Battista, M. Kaufmann, T. Mchedlidze, V. Roselli, C. Squarcella (2012) Small Point Sets for Simply-Nested Planar Graphs. In: M.van Kreveld, B.Speckmann, 19th International Symposium on Graph Drawing (GD '11), Springer, vol. 7034 of LNCS, pp. 75-85.

  26. P. Angelini, W. Didimo, S. Kobourov, T. Mchedlidze, V. Roselli, A. Symvonis, S. Wismath (2012) Monotone Drawings of Graphs with Fixed Embedding. In: M. van Kreveld, B. Speckmann, eds., 19th International Symposium on Graph Drawing (GD '11), Springer, vol. 7034 of LNCS, pp. 379-390.

  27. P. Angelini, G. Di Battista, F. Frati (2011) Simultaneous Embedding of Embedded Planar Graphs. In: T. Asano, S.-I. Nakano, Y. Okamoto, O. Watanabe, eds., 22nd International Symposium on Algorithms and Computation (ISAAC '11), Springer, vol. 7074 of LNCS, pp. 271-280.

  28. P. Angelini, G. Di Battista, W. Didimo, F. Frati, S.-H. Hong, M. Kaufmann, G. Liotta, A. Lubiw (2011) RAC and LAC drawings of planar graphs in subquadratic area. In: A. Marquez, P. Ramos, J. Urrutia, eds., 14th Spanish Meeting on Computational Geometry (EGC '11), Centre de Recerca Matematica, vol. 8 of Documents, pp. 125-128.

  29. P. Angelini, T. Bruckdorfer, M. Chiesa, F. Frati, M. Kaufmann, C. Squarcella (2011) On the Area Requirements of Euclidean Minimum Spanning Trees. In: F. Dehne, J. Iacono, J.-R. Sack, eds., 12th Algorithms and Data Structures Symposium (WADS '11), Springer, vol. 6844 of LNCS, pp. 25-36.

  30. P. Angelini, G. Di Battista, F. Frati, M. Patrignani, I. Rutter (2011) Testing the Simultaneous Embeddability of Two Graphs whose Intersection is a Biconnected Graph or a Tree. In: C.S. Iliopoulos, W.F. Smyth, eds., Workshop on Combinatorial Algorithms (IWOCA '10), Springer, vol. 6460 of LNCS, pp. 212-225.

  31. P. Angelini, M. Geyer, M. Kaufmann, D. Neuwirth (2011) On a Tree and a Path with no Geometric Simultaneous Embedding. In: U. Brandes, S. Cornelsen, eds., 18th International Symposium on Graph Drawing (GD '10), Springer, vol. 6502 of LNCS, pp. 38-49.

  32. P. Angelini, E. Colasante, G. Di Battista, F. Frati, M. Patrignani (2011) Monotone Drawings of Graphs. In: U. Brandes, S. Cornelsen, eds., 18th International Symposium on Graph Drawing (GD '10), Springer, vol. 6502 of LNCS, pp. 13-24.

  33. P. Angelini, F. Frati, M. Geyer, M. Kaufmann, T. Mchedlidze, A. Symvonis (2011). Upward Geometric Graph Embeddings into Point Sets. In: U. Brandes, S. Cornelsen, eds., 18th International Symposium on Graph Drawing (GD '10), Springer, vol. 6502 of LNCS, pp. 25-37.

  34. P. Angelini, G. Di Battista, F. Frati, V. Jelinek, J. Kratochvil, M. Patrignani, I. Rutter (2010) Testing Planarity of Partially Embedded Graphs. In: M.Charikar, ed., 21st Symposium On Discrete Algorithms (SODA '10), ACM-SIAM, pages 202-221.

  35. P. Angelini, G. Di Battista, F. Frati (2010) Succinct Greedy Drawings Do Not Always Exist. In: D. Eppstein, E.R. Gansner, eds., 17th International Symposium on Graph Drawing (GD '09), Springer, vol. 5849 of LNCS, pp. 171-182.

  36. P. Angelini, F. Frati, M. Patrignani (2010) Splitting Clusters To Get C-Planarity. In: D. Eppstein, E.R. Gansner, eds., 17th International Symposium on Graph Drawing (GD '09), Springer, vol. 5849 of LNCS, pp. 57-68.

  37. P. Angelini, L. Cittadini, G. Di Battista, W. Didimo, F. Frati, M. Kaufmann, A. Symvonis (2010) On the Perspectives Opened by Right Angle Crossing Drawings. In: D. Eppstein, E.R. Gansner, eds., 17th International Symposium on Graph Drawing (GD '09), Springer, vol. 5849 of LNCS, pp. 21-32.

  38. P. Angelini, F. Frati (2010) Acyclically 3-Colorable Planar Graphs. In: Md.S.Rahman, S.Fujita, eds., Workshop on Algorithms and Computation (WALCOM '10), vol. 5942 of LNCS, pp. 113-124.

  39. P. Angelini, F. Frati, M. Kaufmann (2009) Straight-line Rectangular Drawings of Clustered Graphs. In: F. Dehne, M.L. Gavrilova, J.-R. Sack, C.D. Toth, eds., 11th Algorithms and Data Structures Symposium (WADS '09), Springer, vol. 5664 of LNCS, pp. 25-36.

  40. P. Angelini, F. Frati, L. Grilli (2009) An Algorithm to Construct Greedy Drawings of Triangulations. In: I.G. Tollis, M. Patrignani, eds., 16th International Symposium on Graph Drawing (GD '08), Springer, vol. 5417 of LNCS, pp. 26-37.

  41. P. Angelini, P.F. Cortese, G. Di Battista, M. Patrignani (2009) Topological Morphing of Planar Graphs. In: I.G. Tollis, M. Patrignani, eds., 16th International Symposium on Graph Drawing (GD '08), Springer, vol. 5417 of LNCS, pp. 145-156.

  42. P. Angelini, G. Di Battista, M. Patrignani (2007) Computing a Minimum-Depth Planar Graph Embedding in O(n^4) Time. In: F. Dehne, J.-R. Sack, N. Zeh, eds., 10th Algorithms and Data Structures Symposium (WADS '07), Springer, vol. 4619 of LNCS, pp. 287-299.

International Conferences without formal Proceedings

  1. P. Angelini, G. Da Lozzo (2014) SEFE = C-Planarity?. In: 9th International Colloquium on Graph Theory and Combinatorics (ICGT '14).

  2. P. Angelini, D. Eppstein, F. Frati, M. Kaufmann, S. Lazard, T. Mchedlidze, M. Teillaud, A. Wolff (2013) Universal Point Sets for Planar Graph Drawings with Circular Arcs. In: 25st Canadian Conference on Computational Geometry (CCCG '13).

Posters at International Conferences

  1. P. Angelini, M.A. Bekos, M. Kaufmann, P. Kindermann, T. Schneck (2016) 1-Fan-Bundle-Planar Drawings. In: M.Noellenburg, Y.Hu, eds., 24th International Symposium on Graph Drawing and Network Visualization (GD '16).

  2. P. Angelini, G. Da Lozzo, G. Di Battista, F. Frati, M. Patrignani, I. Rutter (2016) On the Relationship between Map Graphs and Clique Planar Graphs. In: E. Di Giacomo, A. Lubiw, eds., 23rd International Symposium on Graph Drawing and Network Visualization (GD '15), Springer, vol. 9411 of LNCS, pp. 548-550. Received the Best Poster Award.

  3. P. Angelini, L. Antonetti Clarucci, M. Candela, M. Patrignani, M. Rimondini, R. Sepe (2013) BGPlay3D: Exploiting the Ribbon Representation to Show the Evolution of Interdomain Routing. In: S. Wismath, A.Wolff, eds., 21st International Symposium on Graph Drawing (GD '13), Springer, vol. 8242 of LNCS, pp. 526-527.

  4. P. Angelini, P.F. Cortese, F. Frati, M. Patrignani, M. Rimondini (2007) The Simultaneous Planarity Game. In: S.-H. Hong, T. Nishizeki, W. Quan, eds., 15th International Symposium on Graph Drawing (GD '07), Springer, vol. 4875 of LNCS.

Participation to Program Committee

  • PC member of the 28th International Symposium on Algorithms and Computation (ISAAC '17).

  • PC member of the 24th International Symposium on Graph Drawing (GD '16).

  • PC member of the 7th International Conference on Information, Intelligence, Systems and Applications (IISA '16), special session on Graph and Network Visualization.

  • PC member of the 22nd International Symposium on Graph Drawing (GD '14).
Anregungen / Kritik Impressum minicms