Best Paper Award pro Felixe Schrödera

Každoroční mezinárodní sympozium Graph Drawing and Network Visualization se zaměřuje na kombinatorické a algoritmické aspekty kreslení grafů a návrhy systémů a rozhraní vizualizace sítí. Na 32. sympoziu, které se konalo 18. – 20. září v rakouské metropoli, vystoupil dr. Schröder s příspěvkem „The Density Formula: One Lemma to Bound them All“. Za stejnojmenný článek zde také převzal ocenění Best Paper Award.

Těžištěm práce dr. Schrödera je teorie grafů a kombinatorická geometrie. V oceněném článku představuje společně s dalšími kolegy nové lemma (pomocné tvrzení) využitelné pro kreslení grafů v rovině a mimo ni. „Naše lemma se dá použít k důkazu omezení tzv. hustoty nerovinných grafů. Grafy jsou v tomto kontextu sítě, kde jsou některé uzly (resp. vrcholy) spojeny přes hrany. Počet hran v různých grafech se pak označuje jako ‚hustota‘. Hustota je důležité téma, protože pokud dokážete, že hran není mnoho, je graf takzvaně řídký, což často znamená, že na nich můžete efektivně spouštět algoritmy,“ vysvětluje dr. Schröder.

V kontextu kreslení grafů jsou nejznámější třídou rovinné grafy. To jsou grafy, kde lze vrcholy nakreslit jako body ve dvourozměrném prostoru a všechny hrany jako úsečky mezi těmito body tak, že se žádné dvě hrany neprotínají – jediný společný bod, který mohou mít, je ten koncový. Ve třídách mimo rovinné grafy to však zcela neplatí. „Například v k-planárních grafech mohou být hrany překříženy, ale jen málokrát (každá nejvýše k-krát), v tzv. pravoúhlých (RAC) grafech může dojít ke křížení hran pouze v pravém úhlu. V našem článku jsme vyslovili a dokázali nové lemma – odvozené téměř přímo ze slavného Eulerova vzorce – a použili jsme jej k uniformnímu důkazu mnoha výsledků o hustotě tříd grafů blízkých rovinným gafům, které již byly známy v literatuře. A s pomocí tohoto lemmatu jsme zodpověděli několik otevřených otázek, jako např. hustotu RAC grafů. Naše technika důkazu je natolik jednoduchá, že jsme do článku mohli zahrnout mnoho výsledků, z nichž všechny nyní mají jednodušší důkaz než dříve (pokud nějaký měly),“ přibližuje dr. Schröder.

Na Katedru aplikované matematiky MFF UK nastoupil loni v listopadu po obhájení doktorského titulu na Technické univerzitě v Berlíně. „Na Matfyzu pracuje řada výborných vědců, s některými z nich jsem spolupracoval už dříve, takže jsem věděl, že přesun do Prahy je dobré rozhodnutí,“ odpovídá dr. Schröder na otázku, proč se rozhodl absolvovat stáž na Univerzitě Karlově ve skupině DiGeo vedené doc. Pavlem Valtrem. Koncem roku jeho úvazek na fakultě končí. „Budu žádat o měsíční prodloužení, ohledně dalších plánů nemám jasno, ale pokud to bude možné, rád bych zůstal blízko Berlína, kde žije většina mé rodiny a přátel,“ nastiňuje mladý vědec.

OPMK