Alain Matthes has produced a package (tkz-berge.sty) which should become THE way to draw graphs in LaTeX. It is built on top of Tikz, and so can be easily integrated with beamer presentations. The package can be dowloaded from here, and the documentation (in French, but very nicely formatted and with lot of examples) can be obtained from here. Alain's packages are all here.

I plan to redraw all my examples using tkz-berge's syntax, but for the time being, I will show code for the dodecahedron above:

\documentclass{article}

\usepackage{tikz}

\usepackage{tkz-berge}

\pagestyle{empty}

\tikzstyle{NormalVertexStyle}=[shape = circle,%

shading = ball,%

ball color = white,%

very thin,

inner sep=3pt,%

draw]

\SetVertexNoLabel

\tikzstyle{EdgeStyle}= [thick,%

double= orange,%

double distance = 1pt]

\begin{document}

\begin{center}

\begin{tikzpicture}

\tikzstyle{every node} = [node distance=1.5cm]

\Vertex(A)

\EA{A}(C) \NO{C}(B) \SO{C}(D)

\tikzstyle{every node} = [node distance=1.2cm]

\EA{B}(F) \NO{F}(E) \SO{F}(G)

\EA{D}(I) \NO{I}(H) \SO{I}(J)

\EA{F}(L) \NO{L}(K) \SO{L}(M)

\EA{I}(O) \NO{O}(N) \SO{O}(P)

\EA{L}(Q)

\tikzstyle{every node} = [node distance=1.5cm]

\SO{Q}(R) \SO{R}(S) \EA{R}(T)

\Edge(A)(B) \Edge(A)(C) \Edge(A)(D)

\Edge(B)(E) \Edge(B)(G)

\Edge(C)(F) \Edge(C)(I)

\Edge(D)(H) \Edge(D)(J)

\Edge(E)(K) \Edge(E)(F) \Edge(F)(M)

\Edge(G)(L) \Edge(G)(H) \Edge(H)(O)

\Edge(I)(N) \Edge(I)(J) \Edge(J)(P)

\Edge(K)(Q) \Edge(K)(L)

\Edge(M)(Q) \Edge(M)(N)

\Edge(T)(Q) \Edge(L)(R)

\Edge(O)(R) \Edge(O)(P)

\Edge(T)(R) \Edge(N)(S)

\Edge(P)(S) \Edge(T)(S)

\end{tikzpicture}

\end{center}

\end{document}

\usepackage{tikz}

\usepackage{tkz-berge}

\pagestyle{empty}

\tikzstyle{NormalVertexStyle}=[shape = circle,%

shading = ball,%

ball color = white,%

very thin,

inner sep=3pt,%

draw]

\SetVertexNoLabel

\tikzstyle{EdgeStyle}= [thick,%

double= orange,%

double distance = 1pt]

\begin{document}

\begin{center}

\begin{tikzpicture}

\tikzstyle{every node} = [node distance=1.5cm]

\Vertex(A)

\EA{A}(C) \NO{C}(B) \SO{C}(D)

\tikzstyle{every node} = [node distance=1.2cm]

\EA{B}(F) \NO{F}(E) \SO{F}(G)

\EA{D}(I) \NO{I}(H) \SO{I}(J)

\EA{F}(L) \NO{L}(K) \SO{L}(M)

\EA{I}(O) \NO{O}(N) \SO{O}(P)

\EA{L}(Q)

\tikzstyle{every node} = [node distance=1.5cm]

\SO{Q}(R) \SO{R}(S) \EA{R}(T)

\Edge(A)(B) \Edge(A)(C) \Edge(A)(D)

\Edge(B)(E) \Edge(B)(G)

\Edge(C)(F) \Edge(C)(I)

\Edge(D)(H) \Edge(D)(J)

\Edge(E)(K) \Edge(E)(F) \Edge(F)(M)

\Edge(G)(L) \Edge(G)(H) \Edge(H)(O)

\Edge(I)(N) \Edge(I)(J) \Edge(J)(P)

\Edge(K)(Q) \Edge(K)(L)

\Edge(M)(Q) \Edge(M)(N)

\Edge(T)(Q) \Edge(L)(R)

\Edge(O)(R) \Edge(O)(P)

\Edge(T)(R) \Edge(N)(S)

\Edge(P)(S) \Edge(T)(S)

\end{tikzpicture}

\end{center}

\end{document}