Let $H=(V_H,E_H)$ be an undirected graph with a subset $E$ of the edge set $E_H$,
where we call the edges in $E$ {\em red edges} and
the edges in $E_H-E$ {\em blue edges}.
An embedding of $H$ into the plane is called an {\em $E$-planar} embedding
if no red edge crosses any other edges whereas
two blue edges may cross.
In this paper, we give a complete characterization of an instance $(H,E)$
that admits no $E$-planar embedding
via forbidden subgraphs with red/blue edges.
Furthermore we design a linear-time algorithm that finds either
an $E$-planar embedding or a forbidden subgraph.
The problem setting can enable us to formulate a problem
of finding a planar embedding of a planar graph $G$
with an additional constraint such that,
for specified sets $S_1,S_2,\ldots,S_k$ of vertices,
all the vertices in each $S_i$ appear along the same facial cycle.
To see this, we regard all edges in $G$ as red edges and
add a star $s_i$ with blue edges $s_i t$, $t\in S_i$ for each $i$.
For example, this allows us to find a planar embedding of a planar graph $G$
such that the rotation systems of some vertices are predetermined.