  We study two variants of \textsc{Maximum Cut}, which we call
\textsc{Connected Maximum Cut} and \textsc{Maximum Minimal Cut}, in this paper.
In these problems, given an unweighted graph, the goal is to compute a maximum
cut satisfying some connectivity requirements. Both problems are known to be
NP-complete even on planar graphs whereas \textsc{Maximum Cut} on planar graphs
is solvable in polynomial time. We first show that these problems are
NP-complete even on planar bipartite graphs and split graphs. Then we give
parameterized algorithms using graph parameters such as clique-width,
tree-width, and twin-cover number. Finally, we obtain FPT algorithms with
respect to the solution size.
