Ileana Streinu

KINARI-Web is an interactive web server for performing rigidity analysis and visually exploring rigidity properties of proteins. It also provides tools for pre-processing the input data, such as selecting relevant chains from PDB files, adding hydrogen atoms and identifying stabilizing interactions. KINARI-Web offers a quick-start option for beginners, and highly customizable features for the experienced user. Chains, residues or atoms, as well as stabilizing constraints can be selected, removed or added, and the user can designate how different chemical interactions should be modeled during rigidity analysis. The enhanced Jmol-based visualizer allows for zooming in, highlighting or investigating different calculated rigidity properties of a molecular structure. KINARI-Web is freely available at http://kinari.cs.umass.edu .

A hypergraph G with n vertices and m hyperedges with d endpoints each is (k, l)-sparse if for all sub-hypergraphs G' on n' vertices and m' edges, m' ≤ kn' − l. For integers k and l satisfying 0 ≤ l ≤ dk − 1, this is known to be a linearly representable matroidal family. Motivated by problems in rigidity theory, we give a new linear representation theorem for the (k, l)-sparse hypergraphs that is natural; i.e., the representing matrix captures the vertex-edge incidence structure of the underlying hypergraph G.

A hypergraph G with n vertices and m hyperedges with d endpoints each is (k,l)-sparse if for all sub-hypergraphs G' on n' vertices and m' edges, m'\le kn'-l. For integers k and l satisfying 0\le l\le dk-1, this is known to be a linearly representable matroidal family. Motivated by problems in rigidity theory, we give a new linear representation theorem for the (k,l)-sparse hypergraphs that is natural; i.e., the representing matrix captures the vertex-edge incidence structure of the underlying hypergraph G.

We describe a new algorithm, the $(k,\ell)$-pebble game with colors, and use it obtain a characterization of the family of $(k,\ell)$-sparse graphs and algorithmic solutions to a family of problems concerning tree decompositions of graphs. Special instances of sparse graphs appear in rigidity theory and have received increased attention in recent years. In particular, our colored pebbles generalize and strengthen the previous results of Lee and Streinu and give a new proof of the Tutte-Nash-Williams characterization of arboricity. We also present a new decomposition that certifies sparsity based on the $(k,\ell)$-pebble game with colors. Our work also exposes connections between pebble game algorithms and previous sparse graph algorithms by Gabow, Gabow and Westermann and Hendrickson.

Sparse graphs and their associated matroids play an important role in rigidity theory, where they capture the combinatorics of generically rigid structures. We define a new family called {\bf graded sparse graphs}, arising from generically pinned (completely immobilized) bar-and-joint frameworks and prove that they also form matroids. We address five problems on graded sparse graphs: {\bf Decision}, {\bf Extraction}, {\bf Components}, {\bf Optimization}, and {\bf Extension}. We extend our {\bf pebble game algorithms} to solve them.

A pseudo-triangle is a simple polygon with three convex vertices, and a pseudo-triangulation is a face-to-face tiling of a planar region into pseudo-triangles. Pseudo-triangulations appear as data structures in computational geometry, as planar bar-and-joint frameworks in rigidity theory and as projections of locally convex surfaces. This survey of current literature includes combinatorial properties and counting of special classes, rigidity theoretical results, representations as polytopes, straight-line drawings from abstract versions called combinatorial pseudo-triangulations, algorithms and applications of pseudo-triangulations.