documentclass{standalone}
usepackage{tikz}
tikzstyle{graph}=[
  every node/.style={circle,fill=black,inner sep=0pt,minimum width=8pt},
  every path/.style={thick}
]
begin{document}
begin{tikzpicture}[graph]
foreach i [evaluate=i as a using 90-(i-1)*360/5] in {1,...,5} {
  node (oi) at (a:2) {};
  node (ii) at (a-36:0.7) {};
}
draw (o1) -- (o2) -- (o3) -- (o4) -- (o5) -- (o1);
draw (i1) -- (i2) -- (i3) -- (i4) -- (i5) -- (i1);
draw (o1) -- (i3); draw (o2) -- (i1); draw (o5) -- (i5);
draw[bend left] (o3) to (i4);
draw[bend right] (o4) to (i2);
end{tikzpicture}
end{document}

documentclass{standalone}
usepackage{tikz}
usetikzlibrary{intersections}
tikzstyle{graph}=[
  every node/.style={circle,fill=black,inner sep=0pt,minimum width=8pt},
  every path/.style={thick},
  crossing/.style={rectangle,fill=red,inner sep=0pt,minimum size=4pt}
]
begin{document}
begin{tikzpicture}[graph]
foreach i [evaluate=i as a using 90-(i-1)*360/5] in {1,...,5} {
  node (oi) at (a:2) {};
  node (ii) at (a-36:0.7) {};
}
draw (o1) -- (o2) -- (o3) -- (o4) -- (o5) -- (o1);
draw[name path=p1] (i1) -- (i2) -- (i3) -- (i4) -- (i5) -- (i1);
draw[name path=p2] (o1) -- (i3);
draw (o2) -- (i1); draw (o5) -- (i5);
draw[name path=p3,bend left] (o3) to (i4);
draw[name path=p4,bend right] (o4) to (i2);
path [name intersections={of=p1 and p2}] (intersection-1) node[crossing] {};
path [name intersections={of=p3 and p4}] (intersection-1) node[crossing] {};
end{tikzpicture}
end{document}

newcommand*edge[1][]{draw[edge,#1]}

newcounter{ngraphpaths}
newcounter{ncrossings}

edge/.append style={increment_ngraphpaths,name path global={cross_pthevalue{ngraphpaths}}},
increment_ngraphpaths/.code={addtocounter{ngraphpaths}{1}},

execute at begin picture={setcounter{ngraphpaths}{0}setcounter{ncrossings}{0}},

execute at end picture={%
ifnum value{ngraphpaths}>1
  pgfmathtruncatemacroaend{value{ngraphpaths}-1}
  foreach a in {1,...,aend}{
    pgfmathtruncatemacrobstart{a+1}
    foreach b in {bstart,...,value{ngraphpaths}}
      path [name intersections={of={cross_pa} and {cross_pb},name=i,total=t}]
        ifnum t>0
          foreach s in {1,...,t}{(i-s) node[crossing] {}}
          pgfextra{addtocounter{ncrossings}{t}}
        fi;
  }
fi
typeout{showcrossings: found thevalue{ncrossings} crossing(s)}}

documentclass{standalone}
usepackage{tikz}
usetikzlibrary{intersections}
tikzstyle{graph}=[
  every node/.style={circle,fill=black,inner sep=0pt,minimum width=8pt},
  edge/.style={thick},
  crossing/.style={rectangle,fill=red,inner sep=0pt,minimum size=4pt}
]
newcommand*edge[1][]{draw[edge,#1]}
newcounter{ngraphpaths}
newcounter{ncrossings}
tikzstyle{showcrossings}=[
  edge/.append style={increment_ngraphpaths,name path global={cross_pthevalue{ngraphpaths}}},
  increment_ngraphpaths/.code={addtocounter{ngraphpaths}{1}},
  execute at begin picture={setcounter{ngraphpaths}{0}setcounter{ncrossings}{0}},
  execute at end picture={%
ifnum value{ngraphpaths}>1
  pgfmathtruncatemacroaend{value{ngraphpaths}-1}
  foreach a in {1,...,aend}{
    pgfmathtruncatemacrobstart{a+1}
    foreach b in {bstart,...,value{ngraphpaths}}
      path [name intersections={of={cross_pa} and {cross_pb},name=i,total=t}]
        ifnum t>0
          foreach s in {1,...,t}{(i-s) node[crossing] {}}
          pgfextra{addtocounter{ncrossings}{t}}
        fi;
  }
fi
typeout{showcrossings: found thevalue{ncrossings} crossing(s)}}
]
begin{document}
begin{tikzpicture}[graph,showcrossings]
foreach i [evaluate=i as a using 90-(i-1)*360/5] in {1,...,5} {
  node (oi) at (a:2) {};
  node (ii) at (a-36:0.7) {};
}
edge (o1) -- (o2) -- (o3) -- (o4) -- (o5) -- (o1);
edge (i1) -- (i2) -- (i3) -- (i4) -- (i5) -- (i1);
edge (o1) -- (i3);
edge (o2) -- (i1); edge (o5) -- (i5);
edge[bend left] (o3) to (i4);
edge[bend right] (o4) to (i2);
end{tikzpicture}
end{document}