Testování rovinnosti částečně nakreslených grafů

Abstrakt

Uvádímelineární algoritmus sloužící k rozhodnutí, zda rovinné nakreslení podgrafu daného grafu je možno doplnit na rovinné nakreslení celého grafu. Dále ukazujeme, že několik přirozených optimalizačních rozšíření této otázky je NP-úplných.

Klíčová slova

• Testování rovinnosti
• částečně nakreslený graf
• NP-úplnost