  Convexity is a notion that has been defined for subsets of $\RR^n$ and for
subsets of general graphs. A convex cut of a graph $G=(V, E)$ is a
$2$-partition $V_1 \dot{\cup} V_2=V$ such that both $V_1$ and $V_2$ are convex,
\ie shortest paths between vertices in $V_i$ never leave $V_i$, $i \in \{1,
2\}$. Finding convex cuts is $\mathcal{NP}$-hard for general graphs. To
characterize convex cuts, we employ the Djokovic relation, a reflexive and
symmetric relation on the edges of a graph that is based on shortest paths
between the edges' end vertices.
  It is known for a long time that, if $G$ is bipartite and the Djokovic
relation is transitive on $G$, \ie $G$ is a partial cube, then the cut-sets of
$G$'s convex cuts are precisely the equivalence classes of the Djokovic
relation. In particular, any edge of $G$ is contained in the cut-set of exactly
one convex cut. We first characterize a class of plane graphs that we call {\em
well-arranged}. These graphs are not necessarily partial cubes, but any edge of
a well-arranged graph is contained in the cut-set(s) of at least one convex
cut. We also present an algorithm that uses the Djokovic relation for computing
all convex cuts of a (not necessarily plane) bipartite graph in $\bigO(|E|^3)$
time. Specifically, a cut-set is the cut-set of a convex cut if and only if the
Djokovic relation holds for any pair of edges in the cut-set.
  We then characterize the cut-sets of the convex cuts of a general graph $H$
using two binary relations on edges: (i) the Djokovic relation on the edges of
a subdivision of $H$, where any edge of $H$ is subdivided into exactly two
edges and (ii) a relation on the edges of $H$ itself that is not the Djokovic
relation. Finally, we use this characterization to present the first algorithm
for finding all convex cuts of a plane graph in polynomial time.
