Can a (directed) tree contain crossing lines?

586 Views Asked by At

Is the graph below a (directed) tree in the mathematical sense, and if it is, is there any precise definition that distinguishes crossing from non-crossig trees?
enter image description here

I think it should be a tree since it is acyclic and connected, but the crossing edges $B - F$ and $C - E$ make me unsure about it - it doesn't look like a "classical" tree, intuitively (presumably because by "classical" tree, I have directed and rooted trees in mind, although I am aware that undirected trees exist, too), and I can not recall having seen such a graph referred to as 'tree' ever before.
Which graph-theoretical classification would apply to this object? Are the distinctions directed vs. undirected, and ordered vs. unordered of relevance here?

Edit: I am thinking that ordering might be of relevance because if you were to "untangle" the lines and align the nodes in such a way that node $F$ is right next to $D$ and $E$ is right next to $G$, the linear order of nodes would be a different one, and that this would make it different tree. Is this correct?

1

There are 1 best solutions below

3
On

As a graph this is the same as the graph where you "uncross" the vertices. Recall the definition of a graph as a set of nodes and a set of edges - it says nothing about the embedding, or the way you draw it.

Your picture is of a tree that is not embedded in the plane. (Though in fact your picture is ambiguous, because the lines connecting vertices do not need to be straight, unless you insist on a piecewise linear embedding into the plane). Trees are always planar, however, which means it is possible to "fix" the drawing so that it is an embedding.

The upshot is that your drawing reflects something about the "embedding" of (the geometric realization) of the graph into the plane. It is not a property of the graph. (The geometric realization refers to the construction by which you build a topological space from a graph - recall, a set of nodes and a set describing the edges - by putting a point for each node and connecting them with intervals if there is an edge between them...)