Kreslení grafů s podmínkami na velikosti stěn

• Thesis title in Czech: Kreslení grafů s podmínkami na velikosti stěn
• Thesis title in English: Graph drawing with constrained face sizes
• Academic year of topic announcement: 2008/2009
• Thesis type: Bachelor's thesis
• Thesis language: čeština
• Department: Department of Applied Mathematics (32-KAM)
• Supervisor: prof. RNDr. Jan Kratochvíl, CSc.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 16.10.2008
• Date of assignment: 16.10.2008
• Date and time of defence: 14.09.2009 00:00
• Date of electronic submission: 14.09.2009
• Date of proceeded defence: 14.09.2009
• Opponents: RNDr. Martin Pergel, Ph.D.

Guidelines

Student se seznámí s dostupnou literaturou o kreslení grafů s dodatečnými podmínkami. Je známo, že existují rovinné grafy, které nejdou nakreslit rovnými čarami tak, aby všechny stěny měly stejný obsah. Student se pokusí vyřešit alespoň jednu z následujících dvou otázek: 1) Charakterizovat rovinné grafy, které mají přímočaré nakreslení pro každé zadání obsahů stěn; 2) Navrhnout algoritmus pro kreslení grafů s použitím Bezierových křivek tak, aby všechny stěny měly stejný obsah, a posoudit estetické kvality takto vygenerovaných nakreslení.

References

C. Thomassen: Plane cubic graphs with prescribed face areas, Combinatorics, Probability and Computing 1 (1992) 371-381

G. di Battista, P. Eades, R. Tamassia, I. D. Tollis: Graph Drawing: Algorithms for the Visualization of Graphs, Prentice-Hall, 1999

Preliminary scope of work

Kreslení grafů s dodatečnými podmínkami.

Preliminary scope of work in English

Graph drawing with additional constraints.