Maurizio Patrignani's Theses & Labs

Maurizio Patrignani
We will be at
Best Paper Award
We will be at
Show all news |
## Drawing Graphs Nicely (with Minimum Depth)## Thesis Outline
## Thesis DescriptionThere 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 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. |