И попробовал убрать все вершины со степенью 1. Сильно лучше не стало, поэтому главный вывод что мне надо перестать мучать matplotlib и найти другой способ отрисовки всей этой ерунды.