Logspace redukce problému orientované dosažitelnosti v grafech vyššího rodu na rovinný případ

Abstrakt

Ukážeme, že dosažitelnost v orientovaných grafech nakreslených na ploše libovolného rodu je logspace-redukovatelná na dosažitelnost v orientovaných grafech nakreslených v rovině.

Klíčová slova

• Dosažitelnost v orientovaných grafech
• log-space redukce
• grafy na plochách