Résumé
Many important graph classes are characterized by means of layouts (a vertex ordering) excluding some patterns. For example, a graph G = (V, E) is a proper interval graph if and only if G has a layoutLsuchthatforeverytripleofverticessuchthatx≺L y≺L z,ifxz∈E,thenxy∈Eand yz ∈ E. Such a triple x, y, z is called an indifference triple. In this paper, we investigate the concept of excluding a set of patterns in tree-layouts rather than layouts. A tree-layout TG = (T,r,ρG) of a graph G = (V,E) is a tree T rooted at some node r and equipped with a one-to-one mapping ρG between V and the nodes of T such that for every edge xy ∈ E, either x is an ancestor of y, denoted x ≺TG y, or y is an ancestor of x. Excluding patterns in a tree-layout is now defined using the ancestor relation. This leads to an unexplored territory of graph classes. In this paper, we initiate the study of such graph classes with the class of proper chordal graphs defined by excluding indifference triples in tree-layouts. Our results combine characterization, compact and canonical representation as well as polynomial time algorithms for the recognition and the graph isomorphism of proper chordal graphs. For this, one of the key ingredients is the introduction of the concept of FPQ-hierarchy generalizing the celebrated PQ-tree data-structure.