Automatically draw nodes at all intersections (for graph crossings)

Question

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}

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:

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!

Answer 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.