Hierarchical decompositions are a useful tool for drawing large graphs. Such decompositions can be represented by means of a data structure called hierarchy tree. In this paper we introduce the notion of P-validity of hierarchy trees with respect to a given property P: this notion reflects the similarity between the topological structure of the original graph and of any high-level representation of it obtained from the hierarchy tree. We study the P-validity when the clustered graph is a tree and property P is the acyclicity, presenting a structure theorem for the P-validity of hierarchy trees under these hypotheses.

On the validity of hierarchical decompositions / Finocchi, Irene; Petreschi, Rossella. - 7th Annual International Computing and Combinatorics Conference (COCOON'01), (2001), pp. 368-374. (7th Annual International Conference on Computing and Combinatorics, Guilin, China, August 20–23, 2001). [10.1007/3-540-44679-6_40].

On the validity of hierarchical decompositions

Irene Finocchi;
2001

Abstract

Hierarchical decompositions are a useful tool for drawing large graphs. Such decompositions can be represented by means of a data structure called hierarchy tree. In this paper we introduce the notion of P-validity of hierarchy trees with respect to a given property P: this notion reflects the similarity between the topological structure of the original graph and of any high-level representation of it obtained from the hierarchy tree. We study the P-validity when the clustered graph is a tree and property P is the acyclicity, presenting a structure theorem for the P-validity of hierarchy trees under these hypotheses.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11385/192713
Citazioni
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 1
social impact