Publikace na Matematicko-fyzikální fakulta |
2010
Abstrakt
Je známo, že každý rovinný graf lze vnořít do roviny tak, že hrany jsou nekřížící se úsečky. Studujeme směrové číslo grafu, které je minimální počet směrů v takovém v noření pro graf s maximálním stupněm Δ.
Ukazujeme, že směrové číslo sériově paralelního grafu maximálního stupně tři je tři. Dále ukazujeme, že směrové číslo u rovinných 3-stromů a částečných rovinných 3-stromů je omezené funkcí 2^O(Δ).
Odpovídáme tím kladně na otázku Dujmoviće a kol. [Computational Geometry 38 (3), pp. 194–212 (2007)], zda lze směrové čislo u vnějškově rovinných grafů omezit pomocí funkce v Δ.