Partitioning planar graph cycles based on chords

Question

Given a cycle of length > 3 in a planar graph, I'm looking to partition it into 4 sublists of length 2 or more such that:

1. No sublist contains two vertices with a chord between them
2. The last element in each sublist is the first element in the next
3. Every element in each sublist is adjacent to its neighbors in the original cycle
4. The difference in size between the sublists is kept minimal, given constraints 1 to 3

Overall I'm not really sure if this is required to be solved using graph structures, or if it's possible to transform it into something more general.

Answer 1

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 < j < k < 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.