Abstrakt
Rozplétání grafů je proces, při kterém pohneme některými vrcholy v nakreslení rovinného grafu tak, abychom dostali rovinné nakreslení, kde hrany jsou úsečky. Cílem je při tom pohnout co nejméně vrcholy.
Ukazujeme algoritmus, který při rozplétání kružnice nechá \Omega(n^{2/3}) vrcholů na svém místě. Dokazujeme také horní mez na počet fixovaných vrcholů pro nejhorší možné počáteční vrcholů grafu G.
Tato mez je funkcí počtu vrcholů, maximálního stupně a průměru grafu G.