Publikace na Matematicko-fyzikální fakulta |
2011
Abstrakt
Abstraktní topologický graf (krátce AT-graf) je dvojice A=(G,R), kde G=(V,E) je graf a R je množina dvojic jeho hran. AT-graf A je jednoduše realizovatelný, pokud G lze nakreslit v rovině tak, že každá dvojice hran z R se kříží právě jednou a žádné jiné dvojice hran se nekříží.
Ukážeme polynomiální algoritmus, který pro daný úplný AT-graf rozhodne, zda je jednoduše realizovatelný. Na druhou stranu ukážeme, že ostatní podobné problémy realizovatelnosti pro (úplné) AT-grafy jsou NP-těžké.