# Partitioning planar graph cycles based on chords

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.

• Since you used the word 'partition', are we to understand that the 4 sublists concatenated together makes the original cycle? – Apiwat Chantawibul Apr 13 '15 at 14:45
• Correct, assuming the last element in each list is removed (point 2). – Aeris130 Apr 13 '15 at 15:04
• What's a chord? Is that the same thing as an edge? – D.W. Apr 13 '15 at 23:53
• Do the sublists have to form a connected subgraph? Or can they just be any set of vertices in the cycle? – Luke Mathieson Apr 14 '15 at 7:33

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).