A hierarchy tree of a graph G is a rooted tree whose leaves are the vertices of G; the internal nodes are usually called clusters. Hierarchy trees are well suited for representing hierarchical decompositions of graphs. In this paper we introduce the notion of P-validity of hierarchy trees with respect to a given graph property P. This notion reflects the similarity between any high-level representation of G obtained from the hierarchy tree and the topological structure of G. Maintaining, the properties of a graph at any level of abstraction is especially relevant in graph drawing applications. We present a structural characterization of P-valid hierarchy trees when the clustered graph is a tree and property P is the acyclicity. Besides being interesting in its own right, our structure theorem can be used in the design of a polynomial time algorithm for recognizing P-valid hierarchy trees.

Structure-preserving hierarchical decompositions / Finocchi, Irene; Petreschi, Rossella. - In: THEORY OF COMPUTING SYSTEMS. - ISSN 1432-4350. - 38:6(2005), pp. 687-700. [10.1007/s00224-004-1132-z]

Structure-preserving hierarchical decompositions

Irene Finocchi;
2005

Abstract

A hierarchy tree of a graph G is a rooted tree whose leaves are the vertices of G; the internal nodes are usually called clusters. Hierarchy trees are well suited for representing hierarchical decompositions of graphs. In this paper we introduce the notion of P-validity of hierarchy trees with respect to a given graph property P. This notion reflects the similarity between any high-level representation of G obtained from the hierarchy tree and the topological structure of G. Maintaining, the properties of a graph at any level of abstraction is especially relevant in graph drawing applications. We present a structural characterization of P-valid hierarchy trees when the clustered graph is a tree and property P is the acyclicity. Besides being interesting in its own right, our structure theorem can be used in the design of a polynomial time algorithm for recognizing P-valid hierarchy trees.
Computational Mathematic, Polynomial Time, Structural Characterization, Topological Structure, Rooted Tree
Structure-preserving hierarchical decompositions / Finocchi, Irene; Petreschi, Rossella. - In: THEORY OF COMPUTING SYSTEMS. - ISSN 1432-4350. - 38:6(2005), pp. 687-700. [10.1007/s00224-004-1132-z]
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/192569
Citazioni
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact