|
|
New Intersection Graph Hierachies
Chmel, Petr ; Jelínek, Vít (vedoucí práce) ; Kratochvíl, Jan (oponent)
String grafy jsou průnikové grafy křivek v rovině. Asinowski a kol. [JGAA 2012] za- definovali hierarchii VPG grafů dle počtů zlomů jednotlivých křivek a ukázali, že tato hierarchie obsahuje právě všechny string grafy. Podobnou hierarchii můžeme pozorovat u k-string grafů: string grafů, jež jsou navíc omezeny tím, že každá dvojice křivek může sdílet nejvýše k bodů. V tomto směru pokračujeme zavedením precisely-k-string grafů, jejichž reprezentace je omezenější, neboť požadujeme, aby každá dvojice křivek sdílela buď právě 0, nebo právě k bodů a zároveň se křivky nesmí jen dotýkat. Dokážeme, že pro každé k ≥ 1 je každý precisely-k-string graf i precisely-(k + 2)-string graf, a že třídy precisely-k-string grafů a precisely-(k + 1)-string grafů jsou inkluzí neporovnatelné. Dále hledáme efektivně reprezentovatelnou třídu průnikových grafů objektů v rovině, která obsahuje všechny grafy s fixním maximálním stupněm. V průběhu zavedeme hi- erarchii průnikových grafů sjednocení d svislých a vodorovných úseček, jež nazýváme impure-d-line grafy, a dalších variant této třídy s omezeními na reprezentaci. Dokážeme, že všechny grafy s maximálním stupněm ≤ 2d jsou impure-d-line grafy a pro d = 1 je toto nejlepší možný výsledek. Také studujeme vztah mezi parametrem d v definici impure-d-line grafů a ostatními grafovými...
|
|
|
Algorithmic aspects of intersection representations
Chmel, Petr ; Jelínek, Vít (vedoucí práce) ; Kratochvíl, Jan (oponent)
Jelikož některé problémy jsou v obecném případě (NP-)těžké, jedním z možných pří- stupů je řešení těchto problémů na omezené třídě grafů. V této práci se zaměřujeme na grafy indukované osově zarovnanými L-tvary, tzv. L-grafy, a podobnou třídu osově zarovnaných L-tvarů a L-tvarů, tzv. {L, L}-grafy, přičemž dva vrcholy jsou spojeny hra- nou, právě když se jejich křivky protínají. Dokazujeme, že rozpoznávání jak L-grafů, tak {L, L}-grafů je NP-úplné. V druhé části práce se zaměřujeme na další obvyklé rozhodovací problémy na L-grafech a příbuzných třídách: nalezení klikovosti, 3-obarvení či nezávislosti grafu.
|
|
| |
host ::
RSS.