Graph Theory in LaTeX

This blog moves

2010-02-26T10:55:00.001-06:00

This blog will continue here, for reasons explained there.

A 3d graph

2009-09-05T11:30:00.002-05:00

... after the example in the tikz gallery.

\usetikzlibrary{calc,3d}
\newcommand{\setxyz}[1]{%
\pgfmathsetmacro{\xone}{cos(180+#1)}%
\pgfmathsetmacro{\yone}{sin(180+#1)}%
\pgfmathsetmacro{\xtwo}{cos(360-#1)}%
\pgfmathsetmacro{\ytwo}{sin(360-#1)}%
}
\setxyz{17}
\begin{tikzpicture}%
[x = {(\xone cm,\yone cm)},
y = {(\xtwo cm,\ytwo cm)},
z = {(0cm,1cm)}]
\GraphInit[vstyle=Shade]
\SetVertexNoLabel
\begin{scope}[canvas is xy plane at z=-5]
\Vertex{x}
\end{scope}
\begin{scope}[canvas is xy plane at z=0]
\grEmptyCycle[prefix=a]{5}
\end{scope}
\EdgeFromOneToAll{x}{a}{}{5}
\Edges(a0,a1,a2,a3,a4,a0)
\begin{scope}[canvas is xy plane at z=5]
\Vertex{y}
\end{scope}
\EdgeFromOneToAll{y}{a}{}{5}
\end{tikzpicture}

A circulant tournament

2009-08-28T16:26:00.006-05:00

This is the circulant C_9(1,2,3,4)

\begin{tikzpicture}
\usepgflibrary{arrows}
\GraphInit[vstyle=Art]
\SetUpEdge[style={->,>=angle 45,bend right=10},color=red]
\grCirculant[RA=3]{9}{1,-2,3,-4}
\end{tikzpicture}

Several options for the \Vertex macro

2009-08-18T19:24:00.003-05:00

UPDATE: This example no longer works with the latest versions of tkz-graph and tkz-berge. For an updated version see this post at my new blog.

\begin{tikzpicture}
\SetVertexNormal[LineColor=brown]
\Vertex[x=0,y=2.5,style=orange,LabelOut=true,Lpos=90]{A}
{\tikzstyle{every node} = [node distance=1.5cm]
\Vertices[x=1.5,y=4,dir=\SO,LabelOut=true,Ldist=5pt]{B,C,D}}
\Vertices[x=3,y=5,dir=\SO,style={shape=coordinate}]{E,F,G,H,I,J}
\Vertices[x=4.5,y=5,dir=\SO,style={font=\bfseries}]{K,L,M,N,O,P}
{\tikzstyle{every node} = [node distance=1.5cm]
\Vertices[x=6,y=4,dir=\SO,
style={line width=2pt,
inner sep=0pt,
text=purple,
fill=yellow,
minimum size=12pt}]{Q,R,S}}
\Vertex[x=7.5,y=2.5,style={shape=rectangle,blue}]{T}
\Edges[color=red,lw=2pt](A,B,E,K,Q,T,S,P,J,D,A)
\Edges(B,G,L,R,T)
\Edges(D,H,O,R)
\Edges(A,C,F,M,Q)
\Edges(C,I,N,S)
\foreach \x/\y in {E/F,G/H,I/J,K/L,M/N,O/P}
{\Edge(\x)(\y)}
\Edge[style={bend left}](G)(N)
\Edge[style={bend right}](A)(T)
\end{tikzpicture}

Several options for the \Edge macro

2009-08-03T20:32:00.003-05:00

\begin{tikzpicture}
\SetVertexNormal
\Vertex[x=0,y=2.5]{A}
{\tikzstyle{every node} = [node distance=1.5cm]
\Vertices[x=1.5,y=4,dir=\SO]{B,C,D}}
\Vertices[x=3,y=5,dir=\SO]{E,F,G,H,I,J}
\Vertices[x=4.5,y=5,dir=\SO]{K,L,M,N,O,P}
{\tikzstyle{every node} = [node distance=1.5cm]
\Vertices[x=6,y=4,dir=\SO]{Q,R,S}}
\Vertex[x=7.5,y=2.5]{T}
\Edges[color=red](A,B,E,K,Q,T,S,P,J,D,A)
\foreach \x/\y in {E/F,G/H,I/J,K/L,M/N,O/P}
{\Edge[color=green](\x)(\y)}
\Edge[style=->](I)(P)
\Edge[style=dashed](A)(C)
\Edge[style=dotted](C)(F)
\Edge[label=CD](C)(D)
\Edge[label=BC,labelcolor=yellow](B)(C)
\Edge[label=QR,labelcolor=orange,labeltext=cyan](Q)(R)
\Edge[label=RS,labelstyle=right](R)(S)
\Edge[label=OS,labelstyle={below=1pt,inner sep=0pt}](O)(S)
\Edge[label=LQ,labelstyle={above,font=\bfseries}](L)(Q)
\Edge[label=FL,labelstyle={font=\tiny\bfseries}](F)(L)
\Edge[label=GN,labelstyle={sloped,above}](G)(N)
\Edge[style={bend right}](A)(T)
\end{tikzpicture}

Simulating KTikZ with Emacs

2009-08-03T00:01:00.014-05:00

I stumbled upon a piece of software called KtikZ. The screenshot in that page, together with the fact that Doc-View mode is included in the new Emacs 23, inspired me to try that idea with tikz2pdf. With help from folks from gnu.emacs.help, I came up with the following function:

(defun split-for-tikz2pdf ()
(interactive)
(TeX-run-style-hooks "tikz")
(TeX-run-style-hooks "tkz-berge")
(split-window-horizontally 60)
(other-window 1)
(split-window-vertically 15)
(find-file "tikz2pdf_temp.pdf")
(doc-view-mode)
(auto-revert-mode 1)
(other-window 1)
(let ((file-path (buffer-file-name)))
(when file-path
(shell)
(comint-send-string (get-buffer-process (current-buffer))
(format "tikz2pdf -v %S \n" file-path))))
)

which gives something like this, when applied at a buffer with a .tex file:

Unfortunately, the buffer for the .pdf file is not in Doc-View mode after executing the function. One has to go to that window and do M-x doc-view-mode. After that, sometimes the picture is not generated correctly and one has to reload manually with g. Other useful Doc-View key bindings are + and -.

You might want to use my simple AucTeX style files tikz.el and tkz-berge.el.

Using tikz2pdf

2008-02-21T12:46:00.004-06:00

When drawing graphs by trial and error, the script tikz2pdf by Hans Meine can be very useful.

I have the following in ~/.tikz2pdf.tex:

\documentclass{article}

\usepackage{tikz}
\usepackage{tkz-berge}

\usepackage[graphics,tightpage,active]{preview}
\PreviewEnvironment{tikzpicture}
\newlength{\imagewidth}
\newlength{\imagescale}

\begin{document}

\input{%s}

\end{document}

Then, I edit a file, say foo.tikz, with

\begin{tikzpicture}
\grHeawood[RA=1]
\end{tikzpicture}

and run

tikz2pdf -v foo.tikz

I can open then the generated tikz2pdf_temp.pdf with, say Sumatra,which is a viewer that, unlike Acrobat, does not complain if an opened file is modified. Next time I modify foo.tikz and save it, pdflatex is automatically run and I can press r in Sumatra to update the picture.

New LaTeX package for graphs

2007-05-10T17:14:00.000-05:00

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}

A mistake in Tutte's 8-cage

2007-02-27T18:45:00.000-06:00

Only after Kjell Magne Fauske posted in his gallery two (much improved) versions of two graphs found here, I realized there is a mistake in my picture of Tutte's 8-cage. There are 5-cycles among the "inner" 10 vertices. Kjell has posted a correct picture.

The largest 3-regular graph of diameter 3

2006-08-31T18:33:00.000-05:00

See this paper

\documentclass{article}
\usepackage{tikz}
\pagestyle{empty}

\begin{document}
\begin{center}
\begin{tikzpicture}[style=thick]
\foreach \x in {18,90,...,306}
{
\draw (\x:4cm) circle (2pt) -- (\x+72:4cm);
\draw (\x:4cm) -- (\x:3cm) circle (2pt);
\draw (\x:3cm) -- (\x+15:2cm) circle (2pt);
\draw (\x:3cm) -- (\x-15:2cm) circle (2pt);
\draw (\x+15:2cm) -- (\x+144-15:2cm);
\draw (\x-15:2cm) -- (\x+144+15:2cm);
}
\end{tikzpicture}
\end{center}
\end{document}

The largest 4-regular graph of diameter 2

2006-08-31T18:28:00.000-05:00

See this paper.

\documentclass{article}
\usepackage{tikz}
\pagestyle{empty}

\begin{document}
\begin{center}
\begin{tikzpicture}[style=thick]
\foreach \x in {0,30,...,330}
{
\draw (\x:2cm) circle (2pt) -- (\x+30:2cm);
}
\foreach \x in {0,60,...,300}
{
\draw (\x:2cm) circle (2pt) -- (\x+90:2cm);
}
\foreach \x in {0,30,...,150}
{
\draw (\x:2cm) circle (2pt) -- (\x+180:2cm);
}
\draw (60:0.7cm) circle (2pt) --
(180:0.7cm) circle (2pt) --
(300:0.7cm) circle (2pt) -- (60:0.7cm);
\end{tikzpicture}
\end{center}
\end{document}

The McGee graph

2006-08-31T18:17:00.000-05:00

\documentclass{article}
\usepackage{tikz}
\pagestyle{empty}

\begin{document}
\begin{center}
\begin{tikzpicture}[style=thick]
\foreach \x in {0,15,...,345}
{
\draw (\x:3cm) circle (2pt) -- (\x+15:3cm);
}
\foreach \x in {0,45,...,135}
{
\draw (\x:3cm) circle (2pt) -- (\x+180:3cm);
}
\foreach \x in {15,60,...,330}
{
\draw (\x:3cm) circle (2pt) -- (\x+105:3cm);
}
\end{tikzpicture}
\end{center}
\end{document}

The Hoffman-Singleton graph

2006-08-30T11:40:00.000-05:00

\documentclass{article}

\pagestyle{empty}
\usepackage{tikz}

\begin{document}

\begin{center}
\begin{tikzpicture}[style=thick,scale=0.5]
\def\pentagon{(18:1cm) circle (4pt) node[above right=-1.75pt]{\tiny $4$} --
(90:1cm) circle (4pt) node[above]{\tiny $0$} --
(162:1cm) circle (4pt) node[above left=-1.75pt]{\tiny $1$} --
(234:1cm) circle (4pt) node[below]{\tiny $2$} --
(306:1cm) circle (4pt) node[below]{\tiny $3$} -- (18:1cm)}
\def\pentagram{(18:1cm) circle (4pt) node[above right=-1.75pt]{\tiny $4$} --
(162:1cm) circle (4pt) node[above left=-1.75pt]{\tiny $1$} --
(306:1cm) circle (4pt) node[below]{\tiny $3$} --
(90:1cm) circle (4pt) node[above]{\tiny $0$} --
(234:1cm) circle (4pt) node[below]{\tiny $2$} -- (18:1cm)}
\draw[yshift=4cm] node{\tiny $P_{0}$} \pentagon;
\draw[xshift=3cm,yshift=4cm] node{\tiny $P_{1}$} \pentagon;
\draw[xshift=6cm,yshift=4cm] node{\tiny $P_{2}$} \pentagon;
\draw[xshift=9cm,yshift=4cm] node{\tiny $P_{3}$} \pentagon;
\draw[xshift=12cm,yshift=4cm] node{\tiny $P_{4}$} \pentagon;
\draw node{\tiny $Q_{0}$} \pentagram;
\draw[xshift=3cm] node{\tiny $Q_{1}$} \pentagram;
\draw[xshift=6cm] node{\tiny $Q_{2}$} \pentagram;
\draw[xshift=9cm] node{\tiny $Q_{3}$} \pentagram;
\draw[xshift=12cm] node{\tiny $Q_{4}$} \pentagram;
\draw (6,-2.5) node%
{Vertex $i$ in $P_{j}$ is joined to vertex $i+jk\!\!\!\!\pmod{5}$ of $Q_{k}$};
\end{tikzpicture}
\end{center}
\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:

Tutte's 8-cage

2006-08-14T11:14:00.000-05:00

The unique smallest cubic graph of girth 8. Drawn from Algebraic Graph Theory by Godsil and Royle, p.72.

\documentclass{article}
\usepackage{tikz}
\pagestyle{empty}

\begin{document}
\begin{tikzpicture}[style=thick]
\foreach \x in {0,36,...,324}
{
\draw (\x:2cm) circle (2pt) -- (\x+144:2cm);
\draw (\x-10:3cm) circle (2pt) -- (\x+5:4cm);
\draw (\x-10:3cm) circle (2pt) -- (\x+36:2cm);
\draw (\x-10:3cm) circle (2pt) -- (\x+170:3cm);
\draw (\x+5:4cm) circle (2pt) -- (\x+41:4cm);
}
\end{tikzpicture}
\end{document}

A complete bipartite graph

2006-08-04T14:01:00.000-05:00

\documentclass{article}
\usepackage{tikz}
\pagestyle{empty}

\begin{document}
\begin{center}
\begin{tikzpicture}[style=thick]
\foreach \x in {0,1,2}
\foreach \y in {0,1,2}
{\draw (\y,0) -- (\x,1);}
\foreach \x in {0,1,2}{
\draw (\x,0) circle (2pt);
\draw (\x,1) circle (2pt);}
\end{tikzpicture}
\end{center}
\end{document}

A cubic tree

2006-08-03T12:43:00.000-05:00

If it could be completed to a cubic graph, it would give a cubic Moore graph of diameter 3. I wish I knew how to produce a similar tree, but growing from an edge instead of from a vertex.

\documentclass{article}
\usepackage{tikz}
\thispagestyle{empty}
\begin{document}
\newcommand{\twochildren}{child{node{\null}} child{node{\null}}}

\begin{tikzpicture}[style=thick,scale=0.5]
\tikzstyle{every node}=[circle,inner sep=2pt,draw]
\tikzstyle{level 1}=[sibling distance=20mm]
\tikzstyle{level 2}=[sibling distance=10mm]
\tikzstyle{level 3}=[sibling distance=5mm]
\node{\null}[grow'=right]
child{node{\null}
child{node{\null}\twochildren}
child{node{\null}\twochildren} }
child{node{\null}
child{node{\null}\twochildren}
child{node{\null}\twochildren} }
child{node{\null}
child{node{\null}\twochildren}
child{node{\null}\twochildren} };
\end{tikzpicture}
\end{document}

Petersen graph

2006-08-02T17:38:00.000-05:00

The smallest cubic graph of girth 5, drawn using TikZ.

\documentclass{article}
\usepackage{tikz}
\pagestyle{empty}

\begin{document}
\begin{center}
\begin{tikzpicture}[style=thick]
\draw (18:2cm) -- (90:2cm) -- (162:2cm) -- (234:2cm) --
(306:2cm) -- cycle;
\draw (18:1cm) -- (162:1cm) -- (306:1cm) -- (90:1cm) --
(234:1cm) -- cycle;
\foreach \x in {18,90,162,234,306}{
\draw (\x:1cm) -- (\x:2cm);
\draw (\x:2cm) circle (2pt);
\draw (\x:1cm) circle (2pt);
}
\end{tikzpicture}
\end{center}
\end{document}

Heawood graph

2006-08-02T14:18:00.000-05:00

The smallest cubic graph of girth 6, or 6-cage, drawn with PS Tricks. This was inspired from the example in The LaTeX Graphics Companion, page 121.

\documentclass{article}
\usepackage{pstricks,pst-node,multido,ifthen,calc}
\pagestyle{empty}

\begin{document}
\begin{center}
\begin{pspicture}(-1,-1.5)(1,1.5)
\psset{unit=1.5cm}
\newcounter{CtA}
\newcounter{Temp}
\newcounter{Tempi}
\SpecialCoor \degrees[14]
\multido{\ia=0+1}{14}{%
\setcounter{CtA}{\ia}%
\addtocounter{CtA}{1}%
\multido{\ib=\value{CtA}+1}{1}{\psline{o-o}(1;\ia)(1;\ib)}
}%
\multido{\ia=0+2}{7}{%
\setcounter{CtA}{\ia}%
\addtocounter{CtA}{5}
\multido{\ib=\value{CtA}+1}{1}{\psline{o-o}(1;\ia)(1;\ib)}
}%
\multido{\i=1+1}{14}{\rput(1;\i){%
\setcounter{Temp}{\i}%
\ifthenelse{\isodd{\value{Temp}}}%
{\setcounter{Tempi}{(\value{Temp}+1)/2}}
{\setcounter{Tempi}{(\value{Temp})/2}}
}%
}
\end{pspicture}
\end{center}
\end{document}

2006-08-02T12:05:00.000-05:00

The purposes of this blog are to show pictures of graphs (where by a graph we mean the object studied in Graph Theory) produced by LaTeX, and more precisely by its packages Xy-pic, PS Tricks and TikZ, and to discuss pros and cons of each approach.

I am using the Perl script texttogif to obtain the PNG pictures from a LaTeX source.