The Complexity of Subtree Intersection Representation of Chordal Graphs and Linear Time Chordal Graph Generation

Tınaz Ekim, Mordechai Shalom, Oylum Şeker

It is known that any chordal graph on $n$ vertices can be represented as the intersection of $n$ subtrees in a tree on $n$ nodes. This fact is recently used in [2] to generate rand…