Characterization of partial 3-trees in terms of three structures

A characterization of partial 3-trees is given based on the elimination sequence of vertices. It is proved that a partial 3-tree contains a vertex set satisfying either of certain three kinds of neighborhood relations on vertices and that a graph is a partial 3-tree if and only if eliminating such a vertex set results in a partial 3-tree. These results yield anO(n ²) time algorithm to recognize 3-trees.