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}
(S_{x}
T_{x})*, then we have the
set

Back to the start page for intersection graphs.

Erich Prisner

made on January 12, 1999