Abstrakt
Ukazujeme, že určit minimální počet vrcholů, jejichž vhodným přesunutím je možno dané nakreslení grafu planarizovat, je NP-těžké a je těžké i aproximovat. Podobný výsledek ukazujeme pro příbuznou úlohu kreslení grafů s nejvýše jedním ohybem na každé hraně.
Nakonec podáváme odhady pro minimální počet planarizujících vrcholů pro stromy a obecné rovinné grafy.