Nowhere-dense classes of graphs
| Thesis title in Czech: | Řídké třídy grafů |
|---|---|
| Thesis title in English: | Nowhere-dense classes of graphs |
| Key words: | teorie řídkých grafů, algoritmické metavěty, dynamické datové struktury |
| English key words: | sparse graph theory, algorithmic metatheorems, dynamic data structures |
| Academic year of topic announcement: | 2011/2012 |
| Thesis type: | diploma thesis |
| Thesis language: | angličtina |
| Department: | Computer Science Institute of Charles University (32-IUUK) |
| Supervisor: | prof. Mgr. Zdeněk Dvořák, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 02.05.2012 |
| Date of assignment: | 02.05.2012 |
| Confirmed by Study dept. on: | 14.05.2012 |
| Date and time of defence: | 02.09.2013 00:00 |
| Date of electronic submission: | 01.08.2013 |
| Date of submission of printed version: | 02.08.2013 |
| Date of proceeded defence: | 02.09.2013 |
| Opponents: | Mgr. Martin Mareš, Ph.D. |
| Guidelines |
| The recently developed concept of nowhere-dense graph classes provides a natural characterization of structural sparsity. Most interesting classes of sparse graphs are nowhere-dense, including planar graphs and other proper minor-closed graph classes, graph classes closed on topological subgraphs and graphs drawn in plane with bounded numbers of crossings on each edge. The thesis will focus on the algorithmic and structural properties of nowhere-dense graph classes, considering especially first-order properties and their generalizations. |
| References |
| J. Nešetřil, P. Ossona de Mendez: Sparsity: Graphs, Structures, and Algorithms, Springer, 2012.
Z. Dvořák, D. Kráľ, R. Thomas: Deciding first-order properties for sparse graphs (Extended abstract), in Proceedings of FOCS'2010, 133-142. H. Gaifman: On local and non-local properties, in: Proc. Herbrands Symp. Logic Coloq., North-Holland, 1982. další časopisecká |