Building a Cotree from a Cograph

Question

What is the criteria for building a cotree from a cograph? All I really know is that the nodes from a cograph G are included as leaves in the cotree, and the internal nodes are labelled alternatingly from 0 and 1. More specifically, I don't understand the leaf groupings. I've included an example below to illustrate the problem.

Answer 1

The rule is that a node labeled $0$ in the cotree corresponds to the "disjoint union" operation. A node labeled $1$ in the cotree corresponds to the "join" operation, which can be thought of as "complement of the disjoint union of the complements".

To see which operation is the top node in the tree, and what the objects on the other side are, it's enough to just check if the graph is connected. If the graph were not connected, then we could:

1. Split the graph $G$ into connected components $G_1, G_2, \dots, G_k$.
2. Draw the cotree for each $G_i$, recursively.
3. Combine those cotrees with a $0$ node.

If the graph is connected, the we know that the top node is a $1$ node, so we do the same thing on the complements:

1. Split the complement $\overline{G}$ into connected components $\overline{G_1}, \overline{G_2}, \dots, \overline{G_k}$.
2. Draw the cotrees for $G_1, G_2, \dots, G_k$, the complements of the connected components we found.
3. Combine those cotrees with a $1$ node.

In your example, the graph we start with is connected. Once we take the complement, we notice that it has two components: one induced by $\{a,b\}$ and one induced by $\{c,d,e,f,g\}$. I've drawn their edges in different colors to make this more clear:

So then our next step will be to find the cotrees for $G_1$ (the subgraph of the original graph $G$ induced by $\{a,b\}$) and $G_2$ (the subgraph of the original graph $G$ induced by $\{c,d,e,f,g\}$), then join them together with a $1$ node. The cotrees of $G_1$ and $G_2$ are found with a similar procedure.

The recursive step is actually easier, because we know that $0$ nodes and $1$ nodes alternate between layers, so in this case we know that both $G_1$ and $G_2$ will be disconnected, and we'll look for their connected components. (The exception is if any of the subgraphs are a single node, in which case we're done with that subtree.)

Answer 2

The above answer gives a top-down method. Let me describe a bottom-up one.

$c$ and $d$ are grouped because their adjacency to other vertices is the same ($c\sim v$ iff $d \sim v$). They are linked together so their parent node is a $1$. Same for $e$ and $f$. Same for $a$ and $b$ but they are not linked. So they have a parent $0$.

To identify second order groupings, merge the first-order groupings into one vertex. You end up with a four-vertex graph over $\{a,b\}$, $\{c,d\}$, $\{e,f\}$, and $g$. It is a star with $\{a,b\}$ in the middle.

In this new graph, you can group $\{c,d\}$, $\{e,f\}$ and $g$ together because they are not linked together and all have the same behavior wrt the other vertex $\{a,b\}$. Their parent vertex will have a zero.

Merging them, you have a graph with two vertices: $\{a,b\}$ and $\{ \{c,d\}, \{e,f\} ,g\}$, and an edge between the two. You can group them with a one as they are linked. You are done.