Connection graphs extend intersection graphs---every intersection graph of a family of P-sets is a connection graph of a family of pairs of P-sets after adding all loops. Therefore recognition for a class of connection graphs may be more difficult than for the corresponding intersection class. For instance, if the property P is to have just one element, then intersection bigraphs, digraphs and graphs are fairly easy to recognize, but recognizing the corresponding connection graphs is NP-complete [CE90]. However, under some minimum degree condition, recognition is again possible essentially by the (bi)clique multigraph method [P97].
Why bicliques? Star graphs for connection graphs still have a slightly more general shape. If we consider any point a xV (Sx Tx), then we have the set V1 of all x V where aSx, and the set V2 of all yV where aTy. Every x V1 is adjacent to every y V2. Note also that V1 and V2 are not necessarily disjoint. Certainly, all xV1 V2 have loops. Finally these subgraphs are not necessarily induced in G, nor are they necessarily maximal.
Back to the start page for intersection graphs.