Well you could try reorganising which nodes you position relative to which
\documentclass{article}
\usepackage{tikz}
\usetikzlibrary{arrows}
\begin{document}
\begin{tikzpicture}[->,>=stealth',auto,node distance=3cm,
thick,main node/.style={circle,fill=black!30,draw,minimum size=1cm,inner sep=0pt]}]
\node[main node] (v) []{$v$};
\node[main node] (2) [below left of =v] {$2$};
\node[main node] (w) [below of =2] {$w$};
\node[main node] (1) [above left of =2] {$1$};
\node[main node] (3) [below of =v] {$3$};
\node[main node] (4) [below right of = 3] {$4$};
\path[-]
(v)
edge node {} (1)
edge node {} (2)
edge node {} (3)
edge node {} (4)
(w)
edge node {} (1)
edge node {} (2)
edge node {} (3)
edge node {} (4);
\end{tikzpicture}
\end{document}

Alternatively, while the relative positioning of TikZ can be quite helpful, if you have a specific position in mind you may like to position nodes explicitly, or use a matrix to place them on a grid a bit more naturally as in the example below.
\documentclass{article}
\usepackage{tikz}
\usetikzlibrary{arrows}
\usetikzlibrary{matrix}
\begin{document}
\begin{tikzpicture}[->,>=stealth',auto,node distance=3cm,
thick,main node/.style={circle,fill=black!30,draw,minimum size=1cm,inner sep=0pt]}]
\matrix (octilinear) [matrix of nodes,nodes={main node},column sep = 2cm,row sep = 2cm]
{
1 & & & V & & \\
& & 2 & 3 & & \\
& & W & & & 4 \\
};
\draw[-] (octilinear-1-1) -- (octilinear-1-4);
\draw[-] (octilinear-1-4) -- (octilinear-2-4);
\draw[-] (octilinear-2-3) -- (octilinear-1-4);
\draw[-] (octilinear-2-3) -- (octilinear-3-3);
\draw[-] (octilinear-3-3) -- (octilinear-3-6);
\draw[-] (octilinear-2-4) -- (octilinear-3-3);
\draw[-] (octilinear-1-1) -- (octilinear-3-3);
\draw[-] (octilinear-1-4) -- (octilinear-3-6);
\end{tikzpicture}
\end{document}

node {}
) in the edge-drawing section can be removed.