Maurizio Patrignani's Theses & Labs

Maurizio Patrignani


Research groups:
  Graph Drawing
  Computer Networks

  By type
  By year
  By topic

  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

Strictly Convex Drawing of Planar Graphs

    Thesis Outline

    Title Type Contact/Supervisor Status Student(s)
    Strictly Convex Drawing of Planar Graphs M Fabrizio Frati
    Maurizio Patrignani

       B = Bachelor (3 year degree)
       M = Master (5 year degree)
       L = Lab (course assignment)

    Thesis Description

    The target is to draw a planar triconnected graph in the minimum area within the straight-line setting and where each face is strictly convex. The known lower bound is Ω(n^3), where n is the number of vertices of the graph.

    All the known algorithms first draw the graph and then perturb the vertices positions. This is rather a naive approach.

    This thesis consists of the following phases:

    1. Bibliographic research on the subjects of triconnected graphs, straight-line drawings, convex polygons.
    2. Proposal of possible approaches and algorithms.
    3. Analytical evaluation of the complexity of the algorithms (if any) or experimental evaluation of a brute-force approach.