Let me say a few words about the reverse problem, where a class G of graphs is given, and we ask for which hypergraphs H of H the intersection graph lies in G . In general, if the hypergraph is given explicitely, we can compute its intersection graph in polynomial time. However, sometimes the hypergraphs are only given implicitely, for instance when the clique hypergraph of a graph is given by the graph itself, or if we represent disks or boxes in d -dimensional space. Then computing the intersection graph may be hard, as it is really the case for clique graphs . Characterization and Recognition via duality For several classes of intersection graphs, recognition algorithms are available.
Examples are interval graphs, chordal graphs, cocomparability graphs, line graphs.
The maybe most natural approach for characterizing and recognizing graphs of some class of intersection graphs uses duality . The key idea is to divide the recognition problem into two separate problems which should be solved separately, but the second after the first. The first subproblem is to find out all star graphs. Obviously, we cannot check all covers of the edge set by complete subgraphs, since their number may be exponential. At first sight you may think that we are done, at least for Scheinerman classes, since all we have to check is whether the hyperedges obey property P .