For the third question: The survey paper of Brandstadt, Le, and Spinrad, Graph Classes: A Survey, SIAM, 1999, contains several graph classes for which GI-completeness is not known. One such class is trapezoid graphs.
Mohammad Al-Turkistany
- 21.1k
- 5
- 66
- 152