Rozmotávání rovinného grafu

Abstrakt

Ukazujeme, že je NP-těžké určit i aproximovat minimální počet vrcholů, které je třeba přemístit, aby se z daného úsečkového nakreslení rovinného grafu vytvořilo nekřížící se nakreslení.

Klíčová slova

• Untangling
• Planar
• Graph