Straight-Line Planarity For Layered Family Trees

Question

Background

I did a bit of genealogy and want to draw my family tree nicely such that persons from the same generation are shown in the same layer and edges don't cross. However, I'm having troubles meeting these constraints and wondered if it is even possible to align my family tree in this way.

I know that my family tree is planar, but that doesn't necessarily mean that it is planar under the constraint »persons from the same generation are shown in the same layer«.

Family Trees

A family tree is a simple, directed acyclic graph with two types of vertices: Persons and (what I call) relationships. Each person has at most one direct predecessor and that direct predecessor is a relationship. Relationships have exactly two direct predecessors and those predecessors are persons.

For an example of a family tree see the graphic below. The yellow boxes are persons and the purple circles are relationships. In this family tree person A and B have the single child E. Person D has two children with E and another child with person C. Person H and I are in a relationship but do not have any children.

Constraints

I want to draw such family trees with two constraints.

1. The drawing is straight-line planar, that is, edges are straight lines and do not cross each other.
   _{Also, nodes have a unique position, that is, you cannot draw all nodes at the same position such that the edges end up with length 0 and therefore don't cross anymore – cheating is not allowed :)}

2. Layering constraint: For all persons $u, v_1, v_2$: If …

   • there is a path of length $n$ from $u$ to $v_1$ and a path of length $n$ from $u$ to $v_2$
   • or there is a path of length $n$ from $v_1$ to $u$ and a path of length $n$ from $v_2$ to $u$

    
   … then $s_1$ and $s_2$ are in the same layer, that is, they are drawn at the same y-coordinate.
   _{Please correct me if I got the layering constraint wrong. I wanted to formalize »persons from the same generation are shown in the same layer«.}

The example from above meets all these constraints.

Negative Examples

There are family trees which are impossible to draw under these constraints. Two examples:

The (incestuous) family tree in next picture cannot meet the layering constraint.
_{Theoretically you could include such relationships in a nice drawing. However, this would likely make the formal definition of »same generations are in the same layer« more complicated (for instance we could assign weights to the edges). As I do not have relationships like this in my family tree we do not have to consider them.}

The family tree in the next picture cannot be drawn straight-line planarly while keeping each generation in one layer. This example also shows that the layering constraint renders Fáry's theorem useless (the theorem states that every simple planar graph is also straight-line planar).

Question

My family tree has 217 vertices, so answering the question »can my family tree be drawn under these constraints« by hand is out of question. Therefore, I want a condition $\varphi$ such that

$\varphi \quad\Leftrightarrow\quad$ family tree $G=(V,E)$ can be drawn under the constraints 1. and 2. from above.

I plan to write a program which then checks $\varphi$ for my family tree. Ideally checking $\varphi$ would be easy to implement. A good time complexity is not important, but the check should be feasible for around 250 vertices.

Of course I would be happy if I also knew how to draw my family tree. But right now the question is just if it can be drawn under these constraints at all.

---

A strong enough $\varphi^+$ or $\varphi^-$ to show either …

$\varphi^+ \quad\Rightarrow\quad$ my family tree can be drawn under the constraints 1. and 2. from above

… or …

$\varphi^- \quad\Rightarrow\quad$ my family tree can not be drawn under the constraints 1. and 2. from above

… would be fine too. However, I cannot share my family tree. Nevertheless, I would be happy to implement your $\varphi^{\pm}$ and check my family tree. Maybe your insights from $\varphi^{\pm}$ help someone other finding a $\varphi$ too.

Answer 1

As you do not have incestuous relationships in your family, you can assign a layer to each vertex, and all lines are between consecutive layers.

The order of the vertices in each layer determines whether lines cross or not. If $A_1 \rightarrow A_2$ and $B_1 \rightarrow B_2$ (with $A_1$, $B_1$ on layer 1, and $A_2$, $B_2$ on layer 2), then the lines cross if and only if the order between $A_1$ and $B_1$ on layer 1 is the same as the order of $A_2$ and $B_2$ on layer 2.

Thus the challenge is to find a permutation of the vertices in each of the layers, such that for each pair of lines between each pair of consecutive layers, the orders of the vertices are correct according to the above characterisation of crossing. If you find such a permutation, then it tells you how to draw your family tree.

More formally, let $L$ be the number of layers. $\varphi$: There exist permutations $\pi_1, \ldots, \pi_L$ of the vertices in each layer such that: $$ A_i \rightarrow A_{i+1} \text{ and } B_i \rightarrow B_{i+1} \Rightarrow \text{sign}\left((\pi_i[A_i] - \pi_i[B_i])(\pi_{i+1}[A_{i+1}] - \pi_{i+1}[B_{i+1}])\right) = 1.$$

The check for $\varphi$ is not hard to implement if time complexity is not important, but be warned that enumerating all permutations and checking the condition for each possibility is probably going to be too slow for your graph on 217 vertices: the number of permutations of $n$ vertices is $n!$.

A simple check that may tell you that your family tree is not drawable according to your constraints is the following. For any pair of relationship nodes $A_i, B_i$ in layer $i$ and $A_j, B_j$ in layer $j$, check if there are paths $A_i \rightarrow A_j$, $A_i \rightarrow B_j$, $B_i \rightarrow A_j$ and $B_i \rightarrow B_j$. If all of these paths exist, then no ordering can prevent lines crossing.