PC-tree

Definition:

A circular-arc graph is the intersection graph of a family of arcs of a circle.

Problem definition:

Given a graph G = (V, E), determine whether the graph is a circular-arc graph.

PC-tree is a data structure used to solve the above problem, discovered by Hsu and McConnell. PC-tree is an unrooted tree, its previous version is called PQ-tree which is discovered by Booth and Lueker in 1976. This article will focus on PC-tree only, because PC-tree is generalization of PQ-tree, which means any problem that can be solved by PQ-tree can reduce to PC-tree problems.

Each circular-arc graph can be represented by a clique matrix. Consider circular arc its corresponding circular-arc graph and clique matrix as follow:


By theorem, a graph is circular-arc iff. its clique matrix must a circular-ones property (proof provide later). Now the problem is focusing on how to check a matrix contains circular one property. PC-tree take the place to solve this problem. Let me introduce what is a PC-tree first.

PC-tree has two kinds of internal node, P-node and C-node (that's why it is called PC-tree). The children of P-node can be arranged in any order (ie. all permutations). Other than P-node, the children of C-node can only be arranged in the original order or its reverse (ie. if it's leaves is "ABC", another possible ordering is "CBA"). PC-tree is built by considering the rows of clique matrix one by one. The outline of the algorithm is as follow:

for each row in clique matrix {

assign the value to each row symbol;

find a Terminal Path to separate 0s and 1s;

align all 1s and 0s to the same side;

split each node on the path into two nodes, one connect to the leaves with 1s and one connect to 0s;

delete the edges of the path and replace with a C-node x;

contract all edges from x to C-node neighbors, and any node has only 2 neighbors.

}

The circular-ones ordering can be discovered from the graph by reading the leaves on PC-tree in clockwise or anti-clockwise. Like the following:
img provide later
The time complexity of the O(|E|) (proof provide later).

Further application is: scheduling jobs, minimum coloring, maximum cliques, planarity test, consecutive-ones, ...