Partitioning planar graph cycles based on chords
If the original cycle has length $n$, there is a straightforward $O(n^5)$ time algorithm: simply guess which vertex each sublist should start at.

In other words, let the original cycle go through the vertices $v_1,v_2,\dots,v_n,v_1$.  Then you can choose indices $i,j,k,l$ (such that $1 \le i &lt; j &lt; k &lt; l \le n$), where the first sublist contains $v_i,v_{i+1},\dots,v_j$, the second sublist contains $v_j,v_{j+1},\dots,v_k$, and so on (assuming index arithmetic wraps around modulo $n$).  There are only ${n \choose 4} \in O(n^4)$ possible choices for $i,j,k,l$, so you can exhaustively try them all and test each one to see whether it meets all your requirements, and then keep whichever one is best (according to your "difference-in-size" metric).

This proves that the problem can be solved in polynomial time.