  In this paper we introduce the 'simultaneous membership problem', defined for
any graph class C characterized in terms of representations, e.g. any class of
intersection graphs. Two graphs G_1 and G_2, sharing some vertices X (and the
corresponding induced edges), are said to be 'simultaneous members' of graph
class C, if there exist representations R_1 and R_2 of G_1 and G_2 that are
"consistent" on X. Equivalently (for the classes C that we consider) there
exist edges E' between G_1-X and G_2-X such that G_1 \cup G_2 \cup E' belongs
to class C.
  Simultaneous membership problems have application in any situation where it
is desirable to consistently represent two related graphs, for example:
interval graphs capturing overlaps of DNA fragments of two similar organisms;
or graphs connected in time, where one is an updated version of the other.
Simultaneous membership problems are related to simultaneous planar embeddings,
graph sandwich problems and probe graph recognition problems.
  In this paper we give efficient algorithms for the simultaneous membership
problem on chordal, comparability and permutation graphs. These results imply
that graph sandwich problems for the above classes are tractable for an
interesting special case: when the set of optional edges form a complete
bipartite graph. Our results complement the recent polynomial time recognition
algorithms for probe chordal, comparability, and permutation graphs, where the
set of optional edges form a clique.
