\documentclass{standalone}
\usepackage{tikz}
\usetikzlibrary{arrows,backgrounds,positioning}
\begin{document}
\def\nodeDist{2.5cm}
\def\arrowType{triangle 60}
\def\fillColor{black!20}
\def\position{0.6}
\tikzstyle{origVertex} = [draw, blue, fill, shape=circle]
\tikzstyle{newVertex} = [draw, red , fill, shape=circle]
\tikzstyle{invisibleVertex} = [shape=circle]
\tikzstyle{origEdge} = [blue]
\tikzstyle{newEdge} = [red, densely dashed]
\tikzstyle{invisibleEdge} = [draw opacity=0]
\begin{tikzpicture}[node distance=\nodeDist,>=\arrowType,semithick]
\node[origVertex] (0) {};
\node[origVertex] (1) [right of=0] {};
\node[origVertex] (2) [below of=1] {};
\node[origVertex] (3) [left of=2] {};
\path (0) edge[origEdge] node[invisibleVertex] (m0) {} (1)
(1) edge[origEdge] node[invisibleVertex] (m1) {} (2)
(2) edge[origEdge] node[invisibleVertex] (m2) {} (3)
(3) edge[origEdge] node[invisibleVertex] (m3) {} (0);
\path (m0) edge[invisibleEdge] (m1)
edge[invisibleEdge, out= 45, in= 45, looseness=3, overlay] node[invisibleVertex, pos=\position] (e0) {} (m1)
(m1) edge[invisibleEdge] (m2)
edge[invisibleEdge, out= -45, in= -45, looseness=3, overlay] node[invisibleVertex, pos=\position] (e1) {} (m2)
(m2) edge[invisibleEdge] (m3)
edge[invisibleEdge, out=-135, in=-135, looseness=3, overlay] node[invisibleVertex, pos=\position] (e2) {} (m3)
(m3) edge[invisibleEdge] (m0)
edge[invisibleEdge, out= 135, in= 135, looseness=3, overlay] node[invisibleVertex, pos=\position] (e3) {} (m0);
\node[invisibleVertex, below=0cm of e0] {};
\node[invisibleVertex, left =0cm of e1] {};
\node[invisibleVertex, above=0cm of e2] {};
\node[invisibleVertex, right=0cm of e3] {};
\end{tikzpicture}
\qquad
\begin{tikzpicture}[node distance=\nodeDist,>=\arrowType,semithick]
\node[origVertex] (0) {};
\node[origVertex] (1) [right of=0] {};
\node[origVertex] (2) [below of=1] {};
\node[origVertex] (3) [left of=2] {};
\path (0) edge[origEdge] node[newVertex] (m0) {} (1)
(1) edge[origEdge] node[newVertex] (m1) {} (2)
(2) edge[origEdge] node[newVertex] (m2) {} (3)
(3) edge[origEdge] node[newVertex] (m3) {} (0);
\path (m0) edge[->, newEdge] (m1)
edge[<-, newEdge, out= 45, in= 45, looseness=3, overlay] node[invisibleVertex, pos=\position] (e0) {} (m1)
(m1) edge[->, newEdge] (m2)
edge[<-, newEdge, out= -45, in= -45, looseness=3, overlay] node[invisibleVertex, pos=\position] (e1) {} (m2)
(m2) edge[->, newEdge] (m3)
edge[<-, newEdge, out=-135, in=-135, looseness=3, overlay] node[invisibleVertex, pos=\position] (e2) {} (m3)
(m3) edge[->, newEdge] (m0)
edge[<-, newEdge, out= 135, in= 135, looseness=3, overlay] node[invisibleVertex, pos=\position] (e3) {} (m0);
\node[invisibleVertex, below=0cm of e0] {};
\node[invisibleVertex, left =0cm of e1] {};
\node[invisibleVertex, above=0cm of e2] {};
\node[invisibleVertex, right=0cm of e3] {};
\begin{scope}[on background layer, overlay]
\fill[fill=\fillColor] (m0. 45) to [out= 45, in= 45, looseness=3] (m1. 45) to (m1.center) to (m0.center) to (m0. 45);
\fill[fill=\fillColor] (m1. -45) to [out= -45, in= -45, looseness=3] (m2. -45) to (m2.center) to (m1.center) to (m1. -45);
\fill[fill=\fillColor] (m2.-135) to [out=-135, in=-135, looseness=3] (m3.-135) to (m3.center) to (m2.center) to (m2.-135);
\fill[fill=\fillColor] (m3. 135) to [out= 135, in= 135, looseness=3] (m0. 135) to (m0.center) to (m3.center) to (m3. 135);
\end{scope}
\end{tikzpicture}
\qquad
\begin{tikzpicture}[node distance=\nodeDist,>=\arrowType,semithick]
\node[invisibleVertex] (0) {};
\node[invisibleVertex] (1) [right of=0] {};
\node[invisibleVertex] (2) [below of=1] {};
\node[invisibleVertex] (3) [left of=2] {};
\path (0) edge[invisibleEdge] node[draw opacity=100, newVertex] (m0) {} (1)
(1) edge[invisibleEdge] node[draw opacity=100, newVertex] (m1) {} (2)
(2) edge[invisibleEdge] node[draw opacity=100, newVertex] (m2) {} (3)
(3) edge[invisibleEdge] node[draw opacity=100, newVertex] (m3) {} (0);
\path (m0) edge[->, newEdge] (m1)
edge[<-, newEdge, out= 45, in= 45, looseness=3, overlay] node[invisibleVertex, pos=\position] (e0) {} (m1)
(m1) edge[->, newEdge] (m2)
edge[<-, newEdge, out= -45, in= -45, looseness=3, overlay] node[invisibleVertex, pos=\position] (e1) {} (m2)
(m2) edge[->, newEdge] (m3)
edge[<-, newEdge, out=-135, in=-135, looseness=3, overlay] node[invisibleVertex, pos=\position] (e2) {} (m3)
(m3) edge[->, newEdge] (m0)
edge[<-, newEdge, out= 135, in= 135, looseness=3, overlay] node[invisibleVertex, pos=\position] (e3) {} (m0);
\node[invisibleVertex, below=0cm of e0] {};
\node[invisibleVertex, left =0cm of e1] {};
\node[invisibleVertex, above=0cm of e2] {};
\node[invisibleVertex, right=0cm of e3] {};
\begin{scope}[on background layer, overlay]
\fill[fill=\fillColor] (m0. 45) to [out= 45, in= 45, looseness=3] (m1. 45) to (m1.center) to (m0.center) to (m0. 45);
\fill[fill=\fillColor] (m1. -45) to [out= -45, in= -45, looseness=3] (m2. -45) to (m2.center) to (m1.center) to (m1. -45);
\fill[fill=\fillColor] (m2.-135) to [out=-135, in=-135, looseness=3] (m3.-135) to (m3.center) to (m2.center) to (m2.-135);
\fill[fill=\fillColor] (m3. 135) to [out= 135, in= 135, looseness=3] (m0. 135) to (m0.center) to (m3.center) to (m3. 135);
\end{scope}
\end{tikzpicture}
\end{document}