Computational Aspects of Problems on Visibility and Disk Graph Representations - Cagirici, Onur (2021)
Dizertace se zaměřuje na dva koncepty široce studované v oblasti výpočetní geometrie. Jsou to viditelnostní grafy a grafy jednotkových disků. V oblasti viditelnosti jsme studovali bezkonfliktní barevné hlídání mnohoúhelníků, pro které jsme získali obecný algoritmus používající $O(n \log^2 n)$ bezkonfliktních barev, a normální barvení vrcholů ve viditelnostním grafu mnohoúhelníku, kde jsme získali algoritmus pro 4-barvení jednoduchého mnohoúhelníku. Mimo to jsme dokázali, že stejný problém barvení pro 5 barev je NP-úplný a že 4-barvení je už NP-úplné na viditelnostních grafech mnohoúhelníků s dírami. Poté jsme se posunuli k novému směru vnímání viditelnostních grafů, který uvažuje omezení reálného světa pro aplikace. Přesněji nedovoluje viditelnost na libovolnou vzdálenost, tedy dva velmi vzdálené objekty se nevidí, i když mezi nimi není fyzická překážka. Pro modelování tohoto omezení jsme zavedli jednotkově-diskové viditelnostní grafy a dokázali, že problém 3 barvení je pak už NP-úpln