Maurizio Patrignani's Theses & Labs

Maurizio Patrignani
Best Paper Award
We will be at
Show all news |
## Strictly Convex Drawing of Planar Graphs## Thesis Outline
- Bibliographic research on the subjects of triconnected graphs, straight-line drawings, convex polygons.
- Proposal of possible approaches and algorithms.
- Analytical evaluation of the complexity of the algorithms (if any) or experimental evaluation of a brute-force approach.
## Thesis DescriptionThe 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: |