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

Drawing Graphs Nicely (with Minimum Depth)

    Thesis Outline

    Title Type Contact/Supervisor Status Student(s)
    Drawing Graphs Nicely (with Minimum Depth) BM Patrizio Angelini
    Maurizio Patrignani
    unassigned

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

    Thesis Description

    There are different ways of drawing a planar graph. This thesis is about a way to choose a specific drawing between others. This problem is one of the most intriguing of the graph drawing research area and known algorithms to produce nice drawings are so complex that are seldom implemented.

    In a planar drawing of a graph the plane is partitioned into faces, connected regions surrounded by edges. One face of the is called the external face and is unbounded. All other faces have finite area and are called internal. One of the criteria that can be used measure the readability of a drawing is the fact that the internal faces should be "near" the external one. In fact, faces that share an edge are called adjacent. Two adjacent face are said to be at distance 1. The concept of distance between faces induces the following problem: is there a way to find a planar drawing such that the maximum distance between an internal face and the external one is minimized?

    This problem was shown to be polynomial by Bienstock and Monma in the paper "On the complexity of embedding planar graphs to minimize certain distance measures" (Algorithmica 5, 93-109, 1990). The purpose of this thesis is to implement and test the algorithm introduced by these authors starting from a pseudo-code description of it.

    The implementation should be in C++ and should be part of the GDToolkit Library.