Produktna struktura gostih grafov / Product Structure of Dense Graphs

Avtorji Dujmović, Joret, Micek, Morin, Ueckerdt in Wood so v svojem temeljnem prispevku “Ravninski grafi imajo omejeno čakalno število” (“Planargraphs have bounded queue-number”) dokazali, da je vsak ravninski graf podgraf močnega krepkega produkta nekega grafa konstantne drevesneširine in neke poti.

Ta rezultat ima široko paleto aplikacij (o katerih bomo podrobneje razpravljali spodaj).

Nedavna prizadevanja Hlinenýja in Jedelskýja so omogočila razširitev te vrste teorije produktne strukture na goste grafe.

To dvostransko sodelovanje je osredotočeno na nadaljnji razvoj teorije produktne strukture za goste grafe, tako s strukturnega kot algoritmičnegavidika, kot tudi na iskanje aplikacij teorije za primerne probleme.

Izbira te teme je motivirana z več vidikov. Prvič, v zadnjih letih se je izkazalo, da je teorija strukture grafov močno in vsestransko orodje za reševanjeproblemov na številnih različnih področjih teorije grafov. Poleg tega obstaja veliko več prostora za nadaljnji razvoj bolj teoretičnih vidikov teorijestrukture grafov, zlasti v primeru gostih grafov.

Drugič, ta projekt je posebej usmerjen k prednostim posameznih raziskovalnih ekspertiz v obeh partnerskih državah, zlasti za izkoriščanje sinergijkomplementarnih prednosti vseh članov projekta.

In their seminal paper “Planar graphs have bounded queue-number” the authors (Dujmovic, Joret, Micek, Morin, Ueckerdt, and Wood) proved that anyplanar graph is a subgraph of a strong product of a graph of constant tree-width and a path.

This result has a wide range of applications (which we discuss more below).

Recent efforts by Hlinený and Jedelský enabled to overcome the problem of lifting this type of product structure theory to dense graphs.

This bilateral cooperation is focused on further developing product structure theory for dense graphs, both from a structural and algorithmic point ofview, as well as finding applications for the theory to suitable problems.

The choice of this topic is motivated by multiple aspects. Firstly, in recent years graph product structure theory has turned out to be a powerful andversatile tool for solving problems in many different areas of graph theory. Additionally, there is much more room to develop the more theoreticaspects of graph product structure theory further, especially in the dense case.

Secondly, this project is especially geared towards the strengths of the respective research terms in both partner countries, in particular to exploitthe synergies of complementary strengths of all members of the project.