Efficient Solution of Connectivity Problems on Hierarchically Defined Graphs

Abstract

Using hierarchical definitions we can describe very large graphs in small spaces. In this paper we discuss how such succinct graph descriptions can be used to speed up the solution of graph problems. We present the bottom-up method that solves graph problems without expanding the hierarchical description. This allows solutions that are efficient in terms of the hierarchical graph description instead of the size of the expanded graph. We exemplify the method by giving efficient solutions to connectivity problems on hierarchical graphs. Our results have applications in computer-aided design for integrated circuit design and other engineering problems.