Theses & Labs offered within the Graph Drawing Group

Graph Drawing

home

People

Topics

Tools

Publications:
 By type
 By year
 By topic

Theses & Labs

Grants

Wikis

Conferences


Included in


21st Annual Best of Computing - Notable Books and Articles

Marco Di Bartolomeo, Yifan Hu. There Is More To Streamgraphs Than Movies - Better Aesthetics via Ordering And Lassoing. Comp. Graph. For., 2016.

PC of


25th International Symposium on Graph Drawing & Network Visualization

September 25-27, 2017

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


2017 MRC Conference on Beyond Planarity: Crossing Numbers of Graphs

June 11-17, 2017

We will be at


12nd Bertinoro Workshop on Graph Drawing

March 05-10, 2017

Best paper award


18th EG/VGTC Conference on Visualization
6-10 June 2016, Groningen, the Netherlands

Marco Di Bartolomeo, Yifan Hu. There Is More To Streamgraphs Than Movies - Better Aesthetics via Ordering And Lassoing.

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
    unassigned

    Legenda:
       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.