ESPALIERS - A GENERALIZATION OF DENDROGRAMS

Dendrograms are widely used to represent graphically the clusters and partitions obtained with hierarchical clustering schemes. Espaliers ar e generalized dendrograms in which the length of horizontal lines is u sed in addition to their level in order to display the values of two c haracteristics of each cluster (e.g., the split and the diameter) inst ead of only one. An algorithm is first presented to transform a dendro gram into an espalier without rotation of any part of the former. This is done by stretching some of the horizontal lines to obtain a diagra m with vertical and horizontal lines only, then cutting off by diagona l lines the parts of the horizontal lines exceeding their prescribed l ength. The problem of finding if, allowing rotations, no diagonal line s are needed is solved by an O(N-2) algorithm where N is the number of entities to be classified. This algorithm is then generalized to obta in espaliers with minimum width and, possibly, some diagonal lines.