Strukturni, optimizacijski in algoritmični problemi v geometrijskih in topoloških predstavitvah grafov

Grafovske modele je moč najti vsepovsod in naraščajoča popularnost raziskav v teoriji grafov je presegla staro prepričanje, da so grafi zgolj matematične diskretne strukture. Gradnja modelov z uporabo zelo velikih grafov se uporablja v najrazličnejših področjih znanosti in tehnike. Klasična teorija grafov obdeluje majhne grafe in njihove lastnosti, a druga področja znanosti dandanes potrebujejo razvoj orodij za delo z zelo velikimi grafi, neskončnimi grafi, slučajnimi grafi in še bolj kompleksnimi objekti, kot so neskončne družine grafov ali grafovske limite. Tako topološka kot geometrijska teorija grafov se ukvarjata s problemi v takšnih družinah objektov, raziskujeta njihovo strukturo in uporabo v teoretičnih in praktičnih problemih optimizacije, algoritmov in podatkovnih struktur. V sklopu projekta se bomo ukvarjali s strukturnimi, optimizacijskimi in algoritmičnimi problemi v geometrijskih in topoloških predstavitvah grafov. V prvem delovnem paketu bomo raziskovali strukturo predstavitev končnih grafov, ki jih lahko razumemo bodisi kot topološke bodisi kot geometrijske strukture. Nadaljevali bomo naše raziskave o strukturi prekrižno kritičnih grafov, širini vložitev grafov in triangulacij v ploskvah. V drugem delovnem paketu bomo obravnavali teorijo limit optimalnih (oz. lokalno optimalnih) grafovskih risb v zvezi z različnimi modeli slučajnih risb grafov. Z razvito strukturno teorijo limit grafovskih risb si obetamo alternativen pogled na asimptotično (morda celo eksaktno) verzijo domneve Harary-Hill-Guy iz leta 1963 in/ali domneve Turan-Zarankiewicz iz leta 1954. S povezavo z geometrijskimi risbami grafov si obetamo napredek v razumevanju Sylvestrovega problema o štirih točkah iz leta 1865. Tretji delovni paket se bo ukvarjal z uporabo strukturnih rezultatov prvih dveh delovnih paketov pri modeliranju in razvoju algoritmov. Kot primer konkretnih povezav navedemo uporabo grafovskih razdalj v problemih usmerjanja tokov, uporabo geometrijskih presečnih grafov pri problemih premikanja agentov in analize slik, limitni grafovski objekti pa se povezujejo s Hebbovim učenjem, psihološkimi modeli optimalne izkušnje in učenjem nevronskih mrež. Med orodji, ki jih bomo uporabljali pri delu na projektu, naj naštejemo Erdősevo verjetnostno metodo, Robertsonovo in Seymourjevo teorijo strukture grafov s prepovedanim minorjem, Szemerédijevo lemo o regularnosti in novejšo teorijo grafovskih limit, ki jo je prvenstveno razvil L. Lovász. Omenjene rezultate bomo prepletli s strukturnimi rezultati grafovskih vložitev in grafovskih risb, ki smo jih razvili sodelavci projekta in njihovi soavtorji (mostovi v grafih, teorija tlakovcev, šiv grafov, specialne podatkovne strukture za predstavitve geometrijskih grafov). V okviru projekta bomo združili znanja projektne skupine in širili meje znanja na teh grafovskih raziskovalnih problemih.