Spectral Sequencing Based on Graph Distance

The construction of linear mesh layouts has found various applications, such as implicit mesh filtering and mesh streaming, where a variety of layout quality criteria, e.g., span and width, can be considered. While spectral sequencing, derived from the Fiedler vector, is one of the best-known heuristics for minimizing width, it does not perform as well as the Cuthill-Mckee (CM) scheme in terms of span. In this paper, we treat optimal mesh layout generation as a problem of preserving graph distances and propose to use the subdominant eigenvector of a

kernel (affinity) matrix for sequencing. Despite the non-sparsity of the affinity operators we use, the layouts can be computed efficiently for large meshes through subsampling and eigenvector extrapolation. Our experiments show that the new sequences obtained outperform those derived from the Fiedler vector, in terms of spans, and those obtained from CM, in terms of widths and other important quality criteria. Therefore, in applications where several such quality criteria can influence algorithm performance simultaneously, e.g., mesh streaming and implicit mesh filtering, the new mesh layouts could potentially provide a better trade-off. 1 Introduction Computing linear mesh layouts is an instance of the graph layout problem [1], where an optimal labeling of the vertices of a given graph is sought. Many op- timization problems, including sparse matrix reordering [2–4], circuit layout [5], DNA sequencing [6], and ranking [7] , are formulated as graph layout problems. Consider a weighted graph G = (V,E,w) with V = {v1,...,vn} the set of vertices, E the set of edges, and w : E → R the edge weights. A (lin- ear) layout of G is a labeling pi of its vertices, pi : V → {1,2,...,n}. For a real number 0 < p < ∞, the p-discrepancy [7] of G with respect to a lay- out pi is defined as σp(G,pi) = ¡Puv∈E wuv|pi(u)−pi(v)|p¢1/p . If p = ∞, then σ∞(G,pi) = maxuv∈E |pi(v)−pi(v)|, and is also called the bandwidth of the layout. The minimum value σp(G) = minpi σp(G,pi),0 < p ≤∞, is called the min-p-sum of the graph G. Another important layout cost measure is vertex separation [1], defined as max1≤i≤n|{pi(u) ≤ i : ∃pi(v) > i,uv ∈ E}|. Intuitively, it measures, at a certain point of the linear layout, the number of edges for which only one 2 R. Liu, H. Zhang and O. van Kaick end vertex has been encountered. In the field of numerical analysis, various mea- sures, such as bandwidth [2], profile or envelope size [3] and workbound [4], are considered for sparse matrix reordering. It turns out that these measures are re- lated to different p-discrepancies of a graph layout, where the matrix of interest can be considered as the adjacency matrix of the graph G. Several problems in geometry processing [8,9] benefit from having an opti- mized mesh layout. A good example is mesh streaming [10], where the span and width, corresponding to bandwidth and vertex separation,...

Website: www.cs.sfu.ca | Filesize: -
No of Page(s): 7
Download Spectral Sequencing Based on Graph Distance - CiteSeer.pdf