OK, I will write here some of mnbvmar's observations with my tiny input. Since this will be rather long, this is more of a rough sketch rather than detailed analysis.

1) If two vertices have equal neighborhoods (in particular, they are not connected to each other), we can remove one. They can be detected using some hashing. From now on we assume our graphs have no such twins. This may sound silly, but we will use it later. Proof is by caseology.

2) We can forget about connectivity requirement. If we find a solution that doesn't fulfill it then it can be transformed to one that fulfills it unless D is empty and C is an independent set (or symetrically with A and B) which can't be the case because C would consist of twins. So in graphs without twins, existences of such partitions with or without connectivity requirement are equivalent and they can be transformed to each other, so these two problems are equally hard.

3) Assume we guessed an edge between A and C. Every vertex now can belong to only two out of four parts. We can express everything easily using 2SAT. However there are two problems. One is that we can't assign all vertices same value because that would result in a partition where one side has one vertex. Second problem is that it has O(n^2) clauses. Apparently both of these issues can be dealt with, but I don't know how.

4) Assume we guessed two vertices a₁, a₂ from A+B and c from C. We will solve problem in O(m) time. We initially put all other vertices into right (C+D) and start moving them from right to left (A+B) if they need to be on left. v needs to be on left part if it is connected to any of vertices from B or if it is connected to any vertex from A but not to all of them. If there are no more vertices that need to be moved we get a valid partition, unless c is the only remaining vertex on right. This can lead to O(nm) solution.

5) Assume we are given two vertices b from B and d from D. We will solve problem in O(m) time. Consider BFS tree from b and mark vertices on path from b to d, call it P. Let T(v) where be a set of vertices u so that last vertex of P on path bu in that tree is v. In P there is exactly one edge ac going from A to C. Assume we guessed it. Then for all v < a we have that T(v) belongs to A+B and for all v > c we have that T(v) belong to D (where x < y means that x is before y on that path). If we guessed it we can merge T( < a) and T( > c) and solve it using algorithm from 4). We can try guessing that edge one by one. If done efficiently, every edge in this graph will be processed constant number of times in all executions of 4) algorithm for all guessed edges, because and edge is important only if it is adjacent to T(a) or T(c) what leads to O(m) solution (if we are given b and d). Maybe this algorithm also works if b is and or even if and , this has not been investigated in details.