1. Kresleni rovinnych grafu na pevnou mnozinu bodu Tematem je zkoumani otazky, kdy dany rovinny graf (resp. rovinna triangulace) muze byt vnoren na nepritelem danou mnozinu bodu v rovine. Je napriklad znamo, ze grafy, ktere je mozno vnorit na libovolnou mnozinu bodu v obecne poloze, jsou prave vnejskove planarni grafy. Lze ocekavat, ze obecna otazka je NP-uplna, a takovy NP-uplnostni dukaz by byl velmi peknym a publikovatelnym vysledkem. Naopak pro nektere specialni grafy (napr. triangulace) by mohly existovat polynomialni algoritmy. Souvisejici otazka opacneho charakteru se pta po realizovatelnosti triangulaci jako metricky minimalnich triangulaci a jeji vypocetni slozitost je tez otevrena. Jedna se tedy o dve temata, stredne tezka.
2. Algoritmy na prunikovych grafech. Prunikove tridy grafu, zvlaste geometrickych objektu v rovine, byly a jsou znacne studovane jak pro sve prakticke aplikace ci alespon motivace, tak pro radu zajimavych teoretickych vlastnosti a otevrenych otazek. Specielne, v rade takovych trid jsou obecne tezke ulohy (nezavislost, barevnost atd.) polynomialne resitelne. Prace by spocivala v hledani co mozna nejostrejsi hranice mezi polynomialnimi a NP-uplnymi variantami zakladnich optimalizacnich uloh z hlediska prunikovych trid grafu.
3. Grafy s omezenou indukovanou vzdalenosti Cicerone a di Stefano definovali tridu grafu BID($k$), parametrizovanou realnym cislem $k$, jako tridu grafu, v nichz pro kazde 2 vrcholy je podil delek nejdelsi a nejkratsi indukovane cesty je spojujic} mensi nebo roven $k$. Motivaci pro studium teto tri}dy grafu jsou otazky smerovani a spolehlivosti v sitich (vcetne internetu). Tridy BID($k$) prinaseji radu zajimavych teoretickych otazek a otevrenych problemu. Mezi ne patri slozitost rozpoznavani pro pevne $k$ (pro $k$ na vstupu je uloha NP-uplna), hypoteza diskretnosti trid pro $k<2$, ci spojitost pro $k>2$. Zajimave by mohlo byt tez studovat analogicke otazky pro orientovane grafy, zde by mohlo byt snazsi se dobrat prvnich originalnich vysledku.
4. Splitting number pro pevne $k$ Operace rozdeleni vrcholu $u$ v grafu znamena rozdelit (libovolne) mnozinu sousedu vrcholu $u$ na dve podmnoziny a nahradit vrchol $u$ dvema nesousednimi vrcholy, z nichz kazdy je spojen hranami s jednou ze vzniklych podmnozin. Nedavno Faria, Figueiredo a Mendoca dokazali, ze je NP-uplne rozhodnout, zda dany graf je mozno prevest na rovinny graf pomoci nejvyse $k$ operaci deleni vrcholu. Pro kazde pevne $k$ je tato uloha polynomialne resitelna, coz plyne z teorie grafovych minoru Robertsona a Seymoura. Tato teorie ale nedava zadny konkretni algoritmus. Nalezeni konkretniho polynomialniho algoritmu je predmetem diplomove prace.
5. Skoro-geodeticke kostry Kostru grafu nazveme $k$-geodetickou, pokud pro kazdou hranu grafu ma elementarni kruznice urcena touto hranou delku nejvyse $k+1$. V takovem pripade je vzdalenost libovolnych dvou vrcholu v kostre nejvyse $k$-krat tak velka jako vzdalenost techto vrcholu v $G$. Slozitost rozhodnout, zda dany graf obsahuje 3-geodetickou kostru, je otevrenym problemem (pro $k=2$ je uloha polynomialni, pro $k>3$ je uloha NP-uplna).
6. Viditelnostni reprezentace grafu I. Dalsi otazky a okruhy problemu souvisejici se specialnimi (geometrickymi) reprezentacemi grafu. Graf G ma viditelnostni reprezentaci v 3-rozmernem prostoru pomoci objektu daneho typu, je-li mozno tyto objekty rozmistit v rovnobeznych rovinach tak, aby kazdy z nich "videl" (ve smeru kolmem na roviny objektu) alespon kousek z kazdeho objektu, se kterym je prislusny vrchol spojen hranou. Ve zkoumanych pripadech jsou objekty uvazovany jako rovnobezna posunuti vychoziho dvojrozmerneho obrazce. Studovany byly zvlaste otazky reprezentovani uplnych grafu. Zde bylo dokazano [Fekete, Houle, Whitesides 1995], ze pomoci kruhu lze reprezentovat libovolne velky uplny graf, zatimco pomoci ctvercu (stejneho rozmeru) lze reprezentovat uplny graf o 7 vrcholech, nikoliv vsak o 8 vrcholech. Pro dalsi pravidelne obrazce (napr. 6-tiuhelnik), resp. pro obdelniky, jsou znamy pouze odhady, jejichz zpresneni by bylo tematem teto diplomove prace. (Tema stredne lehke az lehke, moznost az nutnost vyuziti pocitacoveho vypoctu.)
7. Viditelnostni reprezentace grafu II. V tomto tematu se jedna o reprezentaci grafu disjunktnimi obdelniky v rovine takovym zpusobem, ze sousedni vrcholy jsou rerezentovany obdelniky, ktere se "vidi" (bud svisle nebo vodorovne). Vi se, ze kazdy planarni graf (a tim spis kazdy strom) ma takovou viditelnostni reprezentaci, kde vsechny hrany jsou reprezentovany viditelnosti v jednom smeru. Znama hypoteza (Dean, Hutchinson) rika, ze kazdy graf stromovitosti 2 (tj. mnozinu hran lze rozdelit na dve mnoziny indukujici stromy) ma vyse definovanou viditelnostni reprezentaci. Uplny dukaz teto hypotezy by byl asi az prilis krasnym vysledkem, ale je mozno ocekavat dilci vysledky. (Spise obtizne tema.)
8. Dotykove grafy mnohouhelniku. Na konferenci Graph Drawing 97 referovali Czyzowicz, Kranakis, Krizanc a Urrutia o dotykovych grafech k-uhelniku v rovine. Jejich clanek obsahuje radu otevrenych otazek co se tyce slozitosti rozpoznavani ruznych trid grafu, jejich inkluzi apod, jakoz i radu nepresnesti v dukazech. Prvnim ukolem by bylo proverit tyto dukazy, muze se stat, ze nektere z dokazovanych tvrzeni neplati. Lehke tema.
9. Kresleni grafu. Testovani a navrhovani algoritmu pro automaticke kresleni grafu. Modifikace pruzinove metody a algoritmy optimalizujici dalsi parametry vysledneho zobrazeni. Teoreticky pocitacovnicka diplomka.