| Meno: | Radoslav
|
|---|
| Priezvisko: | Fulek
|
|---|
| Názov: | Konvexné priesečníkové čísla vybraných tried grafov
|
|---|
| Vedúci: | RNDr. Ondrej Sýkora, DrSc.
|
|---|
| Rok: | 2005
|
|---|
| Blok: | MMI
|
|---|
| Kľúčové slová: | graf, konvexné priesečníkové číslo grafu, konvexné nakreslenie grafu, Halinov graf, mriežky, simulované žíhanie
|
|---|
| Abstrakt: | Konvexné priesečníkové číslo grafu nám udáva
minimálny počet dvojíc pretínajúcich sa hrán grafu, ak je nakreslený tak,
že jeho vrcholy umiestníme na kružnicu a
hrany kreslíme ako úsečky medzi nimi (konvexné nakreslenie grafu).
V mojej práci podám jeho
všeobecný dolný odhad, pre planárne grafy a mriežky M x N jeho horný odhad,
pre niektoré triedy grafov (Halinov graf, mriežku 3 x N)
presné výsledky konvexných priesečníkových čísel, všeobecný prehľad
dosiahnutých výsledov v tejto oblasti a uvediem konvexné
nakreslenie grafu do kontextu iných grafových nakreslení
a algoritmov na získavanie konvexných nakreslení grafov s
čo najmenším počtom priesečníkov.
|
|---|