INTERSECTION GRAPHS OF PROPER SUBTREES OF UNICYCLIC GRAPHS

A graph is fraternally oriented iff for every three vertices u, upsilo n, w the existence of the edges u --> w and upsilon --> w implies that u and v are adjacent. A directed unicyclic graph is obtained f rom a unicyclic graph by orienting the unique cycle clockwise and by orienti ng the appended subtrees from the cycle outwardly. Two directed subtre es s, t of a directed unicyclic graph are proper if their union contai ns no (directed or undirected) cycle and either they are disjoint or o ne of them s has its root r(s) in t and contains all the successors of r(s) in t. In the present paper we prove that G is an intersection gr aph of a family of proper directed subtrees of a directed unicyclic gr aph iff it has a fraternal orientation such that for every vertex upsi lon, G(GAMMA(in)upsilon) is acyclic and G(GAMMA(out)upsilon) is the tr ansitive closure of a tree. We describe efficient algorithms for recog nizing when such graphs are perfect and for testing isomorphism of pro per circular-arc graphs. (C) 1994 John Wiley & Sons, Inc.