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]
|Titolo:||Structure-preserving hierarchical decompositions|
|Data di pubblicazione:||2005|
|Citazione:||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]|
|Appare nelle tipologie:||01.1 - Articolo su rivista (Article)|