Publikace na Matematicko-fyzikální fakulta |
2007
Abstrakt
Podáváme polynomiální algoritmus pro rozpoznávání tzv. polygon-circle grafů bez krátkých kružnic. Tento výsledek je prvním v započatém studování otázky, zda i pro jiné třídy geometrických průnikových grafů může předpoklad neexistence krátkých cyklů vést k polynomiálním algoritmům.