# Why does PGF/TikZ 3.0 draw my simple layered graph as non-planar by default?

I have two questions:

1. If I’m reading §30.4 “Crossing Minimization” of the PGF/TikZ 3.0 manual correctly, the layered graph drawing algorithm should have crossing minimization enabled by default. So why doesn’t the algorithm automatically choose a planar embedding for this graph?
2. What is the best way to tell the algorithm to avoid the edge crossing in this graph? In this case, I specifically want C to be positioned to the left of B and its children (all in gray), without changing other attributes of the graph (as in percusse’s answer).

\documentclass{article}
\usepackage{tikz}
\usetikzlibrary{graphs, graphdrawing}
\usegdlibrary{layered}

\begin{document}
\tikz [gr/.style={gray!50}, font=\bfseries]
\graph [layered layout] {
% Swapping the next two lines removes the edge crossing, but
% it doesn’t make much sense, and also isn’t what I want.
A -- C -- F,
{ [nodes=gr, edges=gr] A -- B -- { E, D -- F } }
};
\end{document}


## Update

I looked again at Pohlmann’s thesis describing his implementation of layered graph drawing for PGF/TikZ. I am now convinced that it is not possible to solve this problem unless you either:

1. manually define minimum layers or weight for all or part of the graph, or
2. reimplement the crossing minimization step of the algorithm (in Lua).

The first item is not preferable in my case, since (a) this problem affects only a small subset of a number of large graphs, and (b) it also defeats the point of using automatic graph layout.

The second is feasible but time-consuming for someone not versed in Lua.

Here are a few quotes from the thesis (emphasis added by me):

Forcing certain edges to have an increased minimum span can sometimes unravel drawings with undesired edge crossings. For this purpose, the modular layered drawing algorithm provides the /graph drawing/layered drawing/minimum layers edge option. (75)

Applied small graphs, the algorithm appears to have no problems generating layered drawings that have only a few edge crossings and bends, even though it does not produce optimal results in all situations—see for instance the drawing of BarthMJ-fig2 where the edge crossing could easily be avoided. Overall, most edges are as short as possible. (102)

For what it’s worth, Mathematica and dot not suffer from this problem:

edges = {"a" -> "c", "c" -> "f", "a" -> "b", "b" -> "e", "b" -> "d", "d" -> "f"};
Row[{LayeredGraphPlot[edges, VertexLabeling -> True, ImageSize -> 100],
Graph[edges /. Rule -> DirectedEdge, VertexLabels -> Placed["Name", Before],
ImagePadding -> 10, ImageSize -> 110]}]

digraph g { a -> c -> f; a -> b; b -> e; b -> d -> f }


## Update 2

I eventually went with setting minimum layers and weight for a single edge, as hinted by esdd’s answer. I was happy enough with this result:

\documentclass{article}
\usepackage{tikz}
\usetikzlibrary{graphs, graphdrawing}
\usegdlibrary{layered}

\begin{document}
\tikz [gr/.style={gray!50}, font=\bfseries]
\graph [layered layout] {
% A and F are horizontally aligned if you also set weight=0.5 for A -- C.
A -- [minimum layers=2] C -- F,
{ [nodes=gr, edges=gr] A -- B -- { E, D -- F } }
};
\end{document}

-
Now I see your edit, may I ask why this is defeating the purpose? I think the output is pretty handsome. And it is still automatic. I think I don't understand your discomfort with the layer settings. –  percusse Apr 20 '14 at 11:08
Please don't use that tag as, unlike Python, we are trying to discourage using old version of TikZ. –  percusse Apr 12 at 20:04
Yes but then what to do if 3.1 comes out 6 months later? –  percusse Apr 12 at 20:52
Yep, for a previous discussion meta.tex.stackexchange.com/questions/4314/… –  percusse Apr 12 at 21:03

Based on percusse's answer you can change the number of minimum layers (e.g. the minimum number of levels that an edge must span) only for the edge from C to F:

\documentclass[tikz,margin=5mm]{standalone}
\usetikzlibrary{graphs, graphdrawing}
\usegdlibrary{layered}

\begin{document}
\tikz [gr/.style={gray!50}, font=\bfseries]
\graph [layered layout] {
A -- C -- F [>minimum layers=2],
{ [nodes=gr, edges=gr] A -- B -- { E, D -- F } },
};
\end{document}


In addition you can set the weight parameter of the edge from D to F to 0:

\documentclass[tikz,margin=5mm]{standalone}
\usetikzlibrary{graphs, graphdrawing}
\usegdlibrary{layered}

\begin{document}
\tikz [gr/.style={gray!50}, font=\bfseries]
\graph [layered layout] {
A -- C -- F [>minimum layers=2],
{ [nodes=gr, edges=gr] A -- B -- { E, D -- F [>weight=0] } },
};
\end{document}


-
Just wanted to note that C -- F [>minimum layers=2] and D -- F [>weight=0] are equivalent to C -- [minimum layers=2] F and D -- [weight=0] F. The former syntax is especially useful, though, to override attributes applied to a subgraph, e.g. D -- [red] { F [>blue], G }. –  hftf Apr 26 '14 at 9:19

I am no graph theory guy but if I kind of understand the algorithm here you need more than one layer to be able to detect crossings. Also notice that minimization is not equal to removing all. So adding more layers looks like working.

\documentclass{article}
\usepackage{tikz}
\usetikzlibrary{graphs, graphdrawing}
\usegdlibrary{layered}

\begin{document}
\tikz [gr/.style={gray!50}, font=\bfseries]
\graph [layered layout,minimum layers=2] {
A -- C -- F,
{ [nodes=gr, edges=gr] A -- B -- { E, D -- F } }
};
\end{document}


-
I believe setting minimum layers=2 on the graph just makes all edges in the graph span at least 2 layers. That the edge crossing has disappeared seems to be more of a coincidence than an actual general solution (especially since this is just one misbehaving subgraph of a much larger graph). Could you explain why it is you think the algorithm requires edges to span multiple layers for crossing minimization to kick in at all? –  hftf Apr 18 '14 at 7:05
@hftf Though I have no idea about the underlying default method, from the description it looks like you need to let the algo scan through the edges layer by layer. At least that's what I understood from the description. It looks too nice to be a coincidence since the E branch looks a little better. If you know about graph theory I would like to know more about these though. –  percusse Apr 18 '14 at 7:47