Theory of Spectral Graph Layout

Graph layout problems appear in many guises. Typically, given edge weights, coordinates are desired for graph vertices such that some distance measure or cost function is minimized. Many routing, partitioning, placement, rendering, and clustering problems can be cast as layout problems. Many of these are NP-hard. For example, the traveling salesman problem can be viewed as a one-dimensional layout problem, with the order of the coordinates representing the order of the cities in a tour, arc weights representing intercity distances, and the cost function being total tour distance. As with many NP-hard problems, a slight change yields a tractable problem: certain quadratic form cost functions can be solved numerically in polynomial space and time. In practice, it can be worthwhile to accept a compromise in the problem statement in exchange for optimality, tractability, and determinism. The alternative is to sacrifice accuracy via some suboptimal approximate solution to the NP-hard problem such as simulated annealing, genetic search, or Kernighan-Lin-type directed-exchange schemes. This paper is about laying out graphs by minimizing the weighted sum of squares of mutual distances, constrained not to vanish always. It has been known for some time that this problem converts into an eigensystem problem. [2]. Numerical techniques for sparse systems and full-storage systems with a novel deflation method are sketched. Application to and implementations for optimal code and data placement are discussed.

tr-94-04.ps
PostScript file

Details

TypeTechReport
NumberMSR-TR-94-04
Pages9
InstitutionMicrosoft Research
> Publications > Theory of Spectral Graph Layout