\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}