Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 4 of 4
Full-Text Articles in Physical Sciences and Mathematics
Periodic Body-And-Bar Frameworks, Ciprian Borcea, Ileana Streinu, Shin-Ichi Tanigawa
Periodic Body-And-Bar Frameworks, Ciprian Borcea, Ileana Streinu, Shin-Ichi Tanigawa
Computer Science: Faculty Publications
Periodic body-and-bar frameworks are abstractions of crystalline structures made of rigid bodies connected by fixed-length bars and subject to the action of a lattice of translations. We give a Maxwell–Laman characterization for minimally rigid periodic body-and-bar frameworks in terms of their quotient graphs. As a consequence we obtain efficient polynomial time algorithms for their recognition based on matroid partition and pebble games.
Enumerating Constrained Non-Crossing Minimally Rigid Frameworks, David Avis, Naoki Katoh, Makoto Ohsaki, Ileana Streinu, Shin-Ichi Tanigawa
Enumerating Constrained Non-Crossing Minimally Rigid Frameworks, David Avis, Naoki Katoh, Makoto Ohsaki, Ileana Streinu, Shin-Ichi Tanigawa
Computer Science: Faculty Publications
In this paper we present an algorithm for enumerating without repetitions all the non-crossing generically minimally rigid bar-and-joint frameworks under edge constraints, which we call constrained non-crossing Laman frameworks, on a given set of n points in the plane. Our algorithm is based on the reverse search paradigm of Avis and Fukuda. It generates each output graph in O(n4) time and O(n) space, or, with a slightly different implementation, in O(n3) time and O(n2) space. In particular, we obtain that the set of all the constrained non-crossing Laman …
Pebble Game Algorithms And Sparse Graphs, Audrey Lee, Ileana Streinu
Pebble Game Algorithms And Sparse Graphs, Audrey Lee, Ileana Streinu
Computer Science: Faculty Publications
A multi-graph G on n vertices is (k,ℓ)-sparse if every subset of n′⩽n vertices spans at most kn′-ℓ edges. G is tight if, in addition, it has exactly kn-ℓ edges. For integer valuesk and ℓ∈[0,2k), we characterize the (k,ℓ)-sparse graphs via a family of simple, elegant and efficient algorithms called the (k,ℓ)-pebble games. [A. Lee, I. Streinu, Pebble game algorithms and sparse graphs, Discrete Math. 308 (8) (2008) 1425–1437] from graphs to hypergraphs.
Planar Minimally Rigid Graphs And Pseudo-Triangulations, Ruth Haas, David Orden, Günter Rote, Francisco Santos, Herman Servatius, Diane Souvaine, Ileana Streinu, Walter Whiteley
Planar Minimally Rigid Graphs And Pseudo-Triangulations, Ruth Haas, David Orden, Günter Rote, Francisco Santos, Herman Servatius, Diane Souvaine, Ileana Streinu, Walter Whiteley
Mathematics Sciences: Faculty Publications
Pointed pseudo-triangulations are planar minimally rigid graphs embedded in the plane with pointed vertices (adjacent to an angle larger than π). In this paper we prove that the opposite statement is also true, namely that planar minimally rigid graphs always admit pointed embeddings, even under certain natural topological and combinatorial constraints. The proofs yield efficient embedding algorithms. They also provide - to the best of our knowledge - the first algorithmically effective result on graph embeddings with oriented matroid constraints other than convexity of faces. These constraints are described by combinatorial pseudo-triangulations, first defined and studied in this paper. Also …