1

I use TikZ to draw (undirected) graphs, but sometimes I would like to be able to mark where all the intersections/crossings are automatically. I understand that the TikZ intersections library has the name intersections= key, but this requires naming all the paths in my graph and then using that key for every pair of paths that intersect (and this is a real pain if I ever need to modify the graph because the pairs of edges that cross might change.) Naming all the paths manually also makes the code significantly less readable.

Q: Is there a way to do this automatically?

For example, here's an embedding of the Petersen graph in TikZ:

\documentclass{standalone}
\usepackage{tikz}
\tikzset{graph/.style={
  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 (o\i) at (\a:2) {};
  \node (i\i) 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}

Petersen graph with 2 crossings

There are two crossings in this embedding. Manually marking the crossings requires something like:

\documentclass{standalone}
\usepackage{tikz}
\usetikzlibrary{intersections}
\tikzset{graph/.style={
  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 (o\i) at (\a:2) {};
  \node (i\i) 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}

Which produces the following output:

Petersen graph with 2 crossings marked

As you might imagine, for more complex graphs this approach runs into readability issues; I would sometimes end up having to name almost all the paths in the drawing and name intersections on dozens of pairs. The ideal case would be if I could just add something like showcrossings to the tikzpicture environment style and have it happen automatically.

I will post my own solution to this, but if anyone can improve on my approach or has a different approach I would be interested!

4
  • Well, in a graph with more than 15 nodes, I don't think your idea is a good one.
    – user156344
    Apr 26, 2019 at 16:11
  • @JouleV I'm using this on graphs 30 nodes and larger with no performance problems. Probably if you have 150 nodes it would be too slow. If you have a better automated solution please post it.
    – codebeard
    Apr 26, 2019 at 16:15
  • I don't have any solution right now, but what I mean is that there are already 15 nodes, and if you don't control your edge careful enough, there would be hundreds of intersections. Well, it is not you who would become confused, but your readers. The compilation speed is not really a problem
    – user156344
    Apr 26, 2019 at 16:17
  • @JouleV I think you have misunderstood the problem. I am interested in finding the "crossing number" of graphs and drawing minimal examples - an important area of graph theory. Obviously for readability you wouldn't want to have more than a few crossings per square cm of the page, but that's up to you to draw the graph in a readable way.
    – codebeard
    Apr 26, 2019 at 16:22

1 Answer 1

1

Here is my solution to this. I hope that others may find it useful.

It boils down to: Automatically name each path in the drawing, then iterate over each pair of named paths and place nodes at any intersections found.

A few gotcha's I found along the way:

  1. At first I thought of using every path/.style={...} or something to name edges automatically. Unfortunately, the \node commands I use to create the vertices end up implicitly creating extra paths and we don't want to find intersections with these. Also for more complex graphs I sometimes use (undrawn) paths to place vertices or helper coordinates and these would interfere if I used every path. To get around this, I defined an \edge command which I used to replace all my drawn \path commands. It's the same as \draw but applies an edge style which we can then define.

    \newcommand*\edge[1][]{\draw[edge,#1]}
    
  2. We need a counter for the number of named paths in the drawing. While I was at it, let's also create a counter so we can store the number of crossings found, in case we are interested in that for some reason (e.g. we could then use that output in the document).

    \newcounter{ngraphpaths}
    \newcounter{ncrossings}
    
  3. In defining the showcrossings style we make each edge increment the counter as well as use name path global. I ended up using global because otherwise if edges are added inside a \foreach or other block of code, they aren't visible at the end of the picture block where we go to find intersections. I am assuming that cross_p is a unique enough prefix to not clash with other things. I also checked and this works even for multiple graphs in the same file; the intersections library just does a \global\let so there's no issue with overwriting the previous names.

    edge/.append style={increment_ngraphpaths,name path global={cross_p\the\value{ngraphpaths}}},
    increment_ngraphpaths/.code={\addtocounter{ngraphpaths}{1}},
    

    We also need to ensure that the counters are reset at the beginning of each picture:

    execute at begin picture={\setcounter{ngraphpaths}{0}\setcounter{ncrossings}{0}},
    
  4. Finally at the end of the picture, if there were at least 2 paths with the edge style, we iterate over each possible pair (except equal pairs* - see note below) and look for intersections. Surprisingly, I haven't found this to be too much of a performance hit, despite being O(n²). Note that we have to check that there is at least one intersection before trying to iterate over them with \foreach. For logging purposes we also print the number of crossings found to the console - this is useful in practice since when trying to draw a graph we often already know what the number of crossings is supposed to be.

    execute at end picture={%
    \ifnum \value{ngraphpaths}>1
      \pgfmathtruncatemacro\aend{\value{ngraphpaths}-1}
      \foreach \a in {1,...,\aend}{
        \pgfmathtruncatemacro\bstart{\a+1}
        \foreach \b in {\bstart,...,\value{ngraphpaths}}
          \path [name intersections={of={cross_p\a} and {cross_p\b},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 \the\value{ncrossings} crossing(s)}}
    

Putting it all together:

\documentclass{standalone}
\usepackage{tikz}
\usetikzlibrary{intersections}
\tikzset{graph/.style={
  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}
\tikzset{showcrossings/.style={
  edge/.append style={increment_ngraphpaths,name path global={cross_p\the\value{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
  \pgfmathtruncatemacro\aend{\value{ngraphpaths}-1}
  \foreach \a in {1,...,\aend}{
    \pgfmathtruncatemacro\bstart{\a+1}
    \foreach \b in {\bstart,...,\value{ngraphpaths}}
      \path [name intersections={of={cross_p\a} and {cross_p\b},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 \the\value{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 (o\i) at (\a:2) {};
  \node (i\i) 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}
*Note on self-crossing paths

In the code above, we never check for intersections of the named path cross_p\a against cross_p\b for equal values of \a and \b. This is despite being able to create a path like \edge (1) -- (2) -- (3) ... that crosses itself. If you do this, the crossing will not be detected by the code above. If you rewrite the foreach loops so that \b starts at \a instead of \a+1, you can get these intersections to be found, but in my testing this only worked for straight paths. As soon as you have some curved paths, it will break and the intersections library will find hundreds of false positive intersections.

In short, if you use this, make sure that each \edge command contains no self-crossings along the path.

3
  • 1
    Please do not get mad at me, this is meant to be a friendly comment. (1) \tikzstyle is deprecated. (2) You could use every path to add a style that auto-names the paths (instead of defining an \edge command. (3) As for self-intersections: can't you just exclude them when you compute the intersections in the loop? (4) Are you aware of the knots library? (Once you replace \tikzstyle by something more appropriate I will be happy to cast an upvote.)
    – user121799
    Apr 26, 2019 at 16:20
  • @marmot Thanks for your comment. (1) According to the author of the answer here, \tikzstyle is still appropriate in some circumstances, that's why I used it: tex.stackexchange.com/questions/52372/… - would you do something else? It's not really an important part of the solution so I don't mind changing it. (2) I explained why every path doesn't work in point 1 of my answer. (3) they are excluded, I was explaining why they need to be. (4) no I was not aware of it, looks interesting but a completely different field of maths.
    – codebeard
    Apr 26, 2019 at 16:31
  • 1
    I've now updated the question and answer to use \tikzset instead.
    – codebeard
    Apr 26, 2019 at 16:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .