Structure-Preserving Hierarchical Decompositions |
| |
Authors: | Irene Finocchi Rossella Petreschi |
| |
Affiliation: | (1) Dipartimento di Informatica, Sistemi e Produzione, Universita degli Studi di Roma "Tor Vergata", Via del Politecnico 1, 00133 Roma , Italy;(2) Dipartimento di Informatica, Universita degli Studi di Roma "La Sapienza", Via Salaria 113, 00198 Roma, Italy |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|