Sylabus
NP-úplnost rozpoznávání (průnikové grafy úseček, konvexních množin a křivek).
Velikosti reprezentací (grafy vynucující reprezentace exponenciální velikosti).
Reprezentovatelnost planárních grafů (Koebeho věta o kruzích, bipartitní grafy jako grafy viditelnosti).
Odhady na barevnost jako funkce klikovosti.
Kreslení rovinných grafů na pevnou množinu bodů. 3-dimenzionální kreslení grafů.
Anotace
Průnikové grafy především geometricky definované - algoritmy a charakterizační věty. Volně navazuje na Geometrické reprezentace grafů I (DMI037).
Vhodné pro 5.ročník a PGS.