A Survey of the Algorithmic Properties of Simplicial, Upper Bound and Middle Graphs - Cheston, Grant; Jap, Tjoen Seng (Journal of Graph Algorithms and Applications, 2006)
Three classes of graphs, simplicial, upper bound, and middlegraphs, have been known for some time, but many of their algorithmicproperties have not been published. The definitions for these graphclasses are reviewed, and theirrelationships with other common graph classes (especially lineand perfect graphs) are presented. Efficient algorithms arereferenced or outlined to recognize each class of graphs.Finally, for each class of graphs and most of the commonparameters of graphs, either an algorithm or an NP-completeresult is presented, or it is referenced in the literature. <!---->