Graph Theory in LaTeX 2

A Cayley graph

June 2, 2012

The following is the Cayley graph $\Gamma(G,S)$ , where $G$ is the additive group of the vector space $V=F^2$ (where $F=\{0,1,2\}$ is the field of three elements), and $S=\{(1,0),(2,0),(0,1),(0,2)\}$ .

\begin{tikzpicture}
  \tikzset{VertexStyle/.style={draw,rectangle}}
  \grEmptyCycle*[rotation=90,prefix=a,RA=2,Math]{{(1,2)},{(0,0)},{(2,1)}}
  \grEmptyCycle*[rotation=90,prefix=b,RA=4.5,Math]{(2,0),(1,0),(1,1),(0,1),(0,2),(2,2)}
  \EdgeInGraphLoop{b}{6}
  \SetUpEdge[style={bend right=10}]
  \EdgeDoubleMod{a}{3}{0}{1}{b}{6}{1}{2}{3}
  \EdgeDoubleMod{a}{3}{0}{1}{b}{6}{2}{2}{3}
  \SetUpEdge[style={bend left=10}]
  \EdgeDoubleMod{a}{3}{0}{1}{b}{6}{4}{2}{3}
  \EdgeDoubleMod{a}{3}{0}{1}{b}{6}{5}{2}{3}    
\end{tikzpicture}

A Cayley graph

Introducing graphiso.sty

May 2, 2012

tags: animation, isomorphism

The purpose of the new package graphiso.sty is to use tkz-graph to produce an animation of a graph isomorphism in a beamer presentation, such as:

You can find documentation and code at Github: rvf0068/graphiso.sty.

An icosahedron in fake 3d

March 10, 2012

tags: 3d, icosahedron

\begin{tikzpicture}
  \begin{scope}[rotate=90]
    \grIcosahedral[form=1,RA=3,RB=1.5]
    \SetUpEdge[color=white,style={double=black,double distance=2pt}]
    \EdgeInGraphLoop{a}{6}
    \EdgeFromOneToSel{a}{b}{0}{1,5}
    \Edges(a2,b1,b3,b5,a4)
    \Edge(a3)(b3)
    \Edges(a1,b1,b5,a5)
    \Edges(a2,b3,a4)
  \end{scope}
\end{tikzpicture}

icosahedron

Options for vertices

October 17, 2011

tags: vertices

This post is an update for this post from my old blog, which did not work with the newer versions of tkz-berge. The changes are:

instead of \tikzstyle{every node} = [node distance=1.5cm] one now has to use the macro: \SetGraphUnit{1.5},
the macro \Vertices needs now an extra argument: {line} (another useful option here is {circle})
the macro \Edges in line 16 needs the extra option local, in order for the other options (the color red) to work.

\begin{tikzpicture}
  \SetVertexNormal[LineColor=brown]
  \Vertex[x=0,y=2.5,style=orange,LabelOut=true,Lpos=90]{A}
  {\SetGraphUnit{1.5}
    \Vertices[x=1.5,y=4,dir=\SO,LabelOut=true,Ldist=5pt]{line}{B,C,D}}
  \Vertices[x=3,y=5,dir=\SO,style={shape=coordinate}]{line}{E,F,G,H,I,J}
  \Vertices[x=4.5,y=5,dir=\SO,style={font=\bfseries}]{line}{K,L,M,N,O,P}
  {\SetGraphUnit{1.5}
    \Vertices[x=6,y=4,dir=\SO,
    style={line width=2pt,
      inner sep=0pt,
      text=purple,
      fill=yellow,
      minimum size=12pt}]{line}{Q,R,S}}
  \Vertex[x=7.5,y=2.5,style={shape=rectangle,blue}]{T}
  \Edges[local,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}

UPDATE For some reason I do not understand, the code above does not work with an updated installation of TeX Live 2011. (It worked for me with the TeX Live 2009 distributed in Ubuntu repositories). The following code produces the intended picture. Until it is figured out why the options to the \Vertex macro do not work well, it seems to be more predictable to use commands instead of options to the macro.

Such commands are defined starting at line 72 of tkz-graph.sty.

\begin{tikzpicture}
  \SetVertexNormal[LineColor=brown]
  {\renewcommand{\VertexLightFillColor}{orange}
    \Vertex[x=0,y=2.5,style=orange,LabelOut=true,Lpos=90]{A}}
  {\SetGraphUnit{1.5}
    \Vertices[x=1.5,y=4,dir=\SO,LabelOut=true,Ldist=5pt]{line}{B,C,D}}
  {\renewcommand{\VertexShape}{coordinate}
    \Vertices[x=3,y=5,dir=\SO]{line}{E,F,G,H,I,J}}
  \Vertices[x=4.5,y=5,dir=\SO,style={font=\bfseries}]{line}{K,L,M,N,O,P}
  {\SetGraphUnit{1.5}
    \renewcommand{\VertexLineWidth}{2pt}
    \renewcommand{\VertexInnerSep}{0pt}
    \renewcommand{\VertexTextColor}{purple}
    \renewcommand{\VertexLightFillColor}{yellow}
    \renewcommand{\VertexInterMinSize}{12pt}
    \Vertices[x=6,y=4,dir=\SO]{line}{Q,R,S}}
  {\renewcommand{\VertexShape}{rectangle}
    \renewcommand{\VertexLightFillColor}{blue}
    \Vertex[x=7.5,y=2.5]{T}}
  \Edges[local,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}

Vertices

Edges on a grid

August 24, 2011

tags: counters, foreach, grid

For drawing some extra edges in a grid I used the following code:

\begin{tikzpicture}
  \newcounter{xp}
  \newcounter{yp}
  \grGrid[prefix=a,RA=2,RB=2]{6}{6}
  \foreach \x in {0,2,4}{%
    \foreach \y in {1,3}{%
      \setcounter{xp}{\x}
      \setcounter{yp}{\y}
      \stepcounter{xp}
      \stepcounter{yp}
      \Edge(a\x;\y)(a\thexp;\theyp)
      }
    }
\end{tikzpicture}

For some reason the following code does not work (producing the error ! Package pgf Error: No shape named a1 is known.) Apparently, only counters are permitted as vertex indices.

\begin{tikzpicture}
  \grGrid[prefix=a,RA=2,RB=2]{6}{6}
  \foreach \x in {0,2,4}{%
    \foreach \y in {1,3}{%
      \pgfmathsetmacro{\xp}{\x+1}
      \pgfmathsetmacro{\yp}{\y+1}
      \Edge(a\x;\y)(a\xp;\yp)
      }
    }
\end{tikzpicture}

The flower snarks

March 10, 2011

tags: macro, snark

I’m using the new rotation option for cycles to define a macro that draws a flower snark. The macro has as optional arguments the radius RA, RB, and RC of the three types of vertices, and a mandatory argument which must be an odd natural number.

\newcommand{\grFlowerSnark}[2][]{%
  \begingroup
  \setkeys[GR]{cl}{#1}%
  \edef\tkzb@rtemp{\cmdGR@cl@RA}
  \edef\tkzb@rtempx{\cmdGR@cl@RB}
  \edef\tkzb@ptemp{\cmdGR@cl@RC}
  \pgfmathsetcounter{tkz@gr@a}{(#2-1)/2}
  \pgfmathsetcounter{tkz@gr@b}{(#2+1)/2}
  \grCycle[RA=\tkzb@ptemp,prefix=b,rotation=90]{#2}
  \grEmptyCycle[RA=\tkzb@rtempx,prefix=a,rotation=90]{#2}
  \pgfmathsetmacro{\smallshift}{360/(5*#2)}
  \grEmptyCycle[RA=\tkzb@rtemp,prefix=c,rotation=90+\smallshift]{#2}
  \grEmptyCycle[RA=\tkzb@rtemp,prefix=d,rotation=90-\smallshift]{#2}
  \EdgeIdentity{a}{b}{#2}
  \EdgeIdentity{a}{c}{#2}
  \EdgeIdentity{a}{d}{#2}
  \Edge(c\thetkz@gr@a)(d\thetkz@gr@b)
  \pgfmathsetcounter{tkz@gr@c}{\thetkz@gr@a-1}
  \pgfmathsetcounter{tkz@gr@d}{\thetkz@gr@b+1}
  {\tikzset{EdgeStyle/.append style = {bend right=90}}
    \EdgeDoubleMod{c}{#2}{0}{1}{c}{#2}{1}{1}{\thetkz@gr@c}
    \EdgeDoubleMod{c}{#2}{\thetkz@gr@b}{1}{c}{#2}{\thetkz@gr@d}{1}{\thetkz@gr@c}
    \EdgeDoubleMod{d}{#2}{0}{1}{d}{#2}{1}{1}{\thetkz@gr@c}
    \EdgeDoubleMod{d}{#2}{\thetkz@gr@b}{1}{d}{#2}{\thetkz@gr@d}{1}{\thetkz@gr@c}
  }
  \Edge[style={bend right=90}](d\thetkz@gr@a)(c\thetkz@gr@b)
  \endgroup
}

So that, for example:

\begin{tikzpicture}
  \SetVertexNormal[MinSize=10pt]
  \grFlowerSnark[RA=4,RB=2.5,RC=1]{5}
\end{tikzpicture}

gives:

Flower snark

The Szekeres snark, more new features

March 9, 2011

tags: cycles, snark

\grEmptyCycle and \grCycle can also have options x and y, that set the coordinates of the center of the cycle, or r and d for polar coordinates (r is the radius and d the angle). Here we use these options together with rotation, in order to draw the Szekeres snark.

\newcounter{in}
\newcounter{nex}
\newcounter{ney}
\begin{tikzpicture}[rotate=90,scale=0.8]
  \SetUpVertex[Style={font=\footnotesize\sffamily}]
  \SetVertexNormal[MinSize=12pt,InnerSep=0pt]
  \grEmptyCycle[prefix=x]{5}
  \foreach \x in  {0,1,...,4}{%
    \setcounter{in}{\x}
    \stepcounter{in}
    \pgfmathsetmacro{\rad}{72*\x}
    \grEmptyCycle[RA=1.65,r=4,d=\rad,prefix=\alph{in},rotation=\rad-160]{9}
    \EdgeInGraphLoop*{\alph{in}}{9}
    \Edge(\alph{in}0)(\alph{in}5)
    \Edge(\alph{in}8)(\alph{in}3)
    \foreach \y in {1,4,7}{%
      \Edge(x\x)(\alph{in}\y)}
  }
  \foreach  \x in  {0,1,...,4}{%
    \setcounter{in}{\x}
    \stepcounter{in}
    \pgfmathsetcounter{nex}{mod(\x+1,5)+1}
    \setcounter{ney}{\thenex}
    \Edge(\alph{in}0)(\alph{ney}8)
    \pgfmathsetcounter{nex}{mod(\x+2,5)+1}
    \setcounter{ney}{\thenex}
    \Edge(\alph{in}6)(\alph{ney}2)
  }
\end{tikzpicture}

Szekeres snark

New versions of tkz-graph and tkz-berge

March 8, 2011

tags: changes, new-version

Finally, the much expected new versions (1.00 c) of tzk-graph and tkz-berge were released by Alain Matthes last week, and can be downloaded from Altermundus download zone.

I expect to post several examples using the new capabilities of the packages. For the time being, I will only say that:

\grCycle (and \grEmptyCycle) has an optional argument rotation that, well, rotates the cycle by the given degrees, hence eliminating the need to use the scope environment.
The commands like \SetUpVertex and \SetVertexNormal accept also several optional arguments, so that one can avoid setting styles with \tikzset.
All of the commands that draw Edges (except \EdgeDoubleMod, that has already nine arguments) can accept optional arguments, changing the look and/or style of the edge.

For example, the line graph of the Petersen graph can be drawn now as:

\begin{tikzpicture}
  \SetUpVertex[Style={font=\footnotesize\sffamily}]
  \SetVertexNormal[MinSize=12pt,InnerSep=0pt]
  \grCirculant[RA=0.6,prefix=a,rotation=-90]{5}{2}
  \grEmptyCycle[RA=1.5,prefix=b,rotation=-18]{5}{2}
  \grCycle[RA=2.5,prefix=c,rotation=18]{5}
  \EdgeIdentity[local,color=red]{a}{b}{5}
  \EdgeIdentity[local,lw=0.5pt]{b}{c}{5}
  {\tikzset{EdgeStyle/.append style = {blue,line width=3pt}}
  \EdgeDoubleMod{b}{5}{0}{1}{a}{5}{2}{1}{5}}
  {\tikzset{EdgeStyle/.append style = {green,line width=2pt}}
  \EdgeDoubleMod{c}{5}{0}{1}{b}{5}{1}{1}{5}}
\end{tikzpicture}

Line graph of the Petersen graph

Doing more with vertices

January 21, 2011

tags: decorations, edges, loops, vertices

The vertices that tkz-berge draws are regular named TikZ nodes, and so they can be used if one wants unusual edges.

Update: I added four more lines, to show that one can also use the node names provided by tkz-berge, to apply extra labels.

Options for vertices

\begin{tikzpicture}
  \usetikzlibrary{decorations.pathmorphing,arrows}
  \tikzset{EdgeStyle/.append style = {line width=2pt}}
  \grEmptyPath[RA=2]{6}
  \draw[line width=3pt] (a0) .. controls (-1,1) and (1,1) .. (a0);
  \draw[thick,color=blue] (a1) .. controls (0,0) and (2,2) .. (a1);
  \draw (a2) .. controls (0,2) and (8,2) .. (a2);
  \shadedraw[top color=brown,opacity=0.8] (a3) circle (0.7cm);
  \draw[thick,decorate,decoration=snake] (a4) -- (a5);
  \draw (a2) node[below]{\textsf{a label}};
  \draw (a3) node[above right=5pt]{$v_{0}$};
  \node (mytext) at (9,1.5) [shape=rectangle,align=center,draw] {a good\\ vertex};
  \draw[->,line width=1pt] (mytext)  -- (a4);
\end{tikzpicture}

The macro \EdgeDoubleMod

January 10, 2011

tags: macro

The macro \EdgeDoubleMod is convenient when drawing some complicated graphs. Consider the following picture of the line graph of the Petersen graph.

Line graph of the Petersen graph

produced by:

\begin{tikzpicture}
  \SetVertexNormal[MinSize=12pt]
  \tikzset{VertexStyle/.append style=
    {inner sep=0pt,font=\footnotesize\sffamily}}
  \begin{scope}[rotate=-90]
    \grCirculant[RA=0.6,prefix=a]{5}{2}
  \end{scope}
  \begin{scope}[rotate=-18]
    \grEmptyCycle[RA=1.5,prefix=b]{5}{2}
  \end{scope}
  \begin{scope}[rotate=18]
    \grCycle[RA=2.5,prefix=c]{5}
  \end{scope}
  \EdgeIdentity{a}{b}{5} 
  \EdgeIdentity{b}{c}{5}
  {\tikzset{EdgeStyle/.append style = {blue,line width=3pt}}
  \EdgeDoubleMod{b}{5}{0}{1}{a}{5}{2}{1}{5}}
  {\tikzset{EdgeStyle/.append style = {green,line width=2pt}}
  \EdgeDoubleMod{c}{5}{0}{1}{b}{5}{1}{1}{5}}
\end{tikzpicture}

We construct the graph using tree cycles: a circulant, an “empty” cycle and a usual cycle. The code \EdgeIdentity{a}{b}{5} just joins, for each $i$ from 0 to 4 (that is, five times) the vertex labeled $a_i$ to the vertex labeled $b_i$ .

Finally \EdgeDoubleMod{b}{5}{0}{1}{a}{5}{2}{1}{5} joins, for each $i$ between 0 and 4 (that is the 5 in the last argument), the vertex labeled $b_{0+1\cdot i}$ to the vertex labeled $a_{2+1\cdot i}$ . In both cases, the sub-index is calculated mod 5 (because of the second and the sixth argument).

Graph Theory in LaTeX 2

Combinatorial graphs drawn using LaTeX

A Cayley graph

Introducing graphiso.sty

An icosahedron in fake 3d

Options for vertices

Edges on a grid

The flower snarks

The Szekeres snark, more new features

New versions of tkz-graph and tkz-berge

Doing more with vertices

The macro \EdgeDoubleMod

Archives

RSS

Using these examples

Tags

Recent Posts

Blogroll

My Dropbox link