Fabrizio Frati's Theses & Labs

Fabrizio Frati


Research groups:
  Graph Drawing

  By type
  By year
  By topic

  Courses (Italian)
  Theses & Labs

We will be at

Beyond-Planar Graphs: Combinatorics, Models and Algorithms;

Feb 24 - Mar 01, 2019

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.