Open Access. Powered by Scholars. Published by Universities.®
Discrete Mathematics and Combinatorics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Discipline
- Keyword
Articles 1 - 10 of 10
Full-Text Articles in Discrete Mathematics and Combinatorics
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.
Common Edge-Unzippings For Tetrahedra, Joseph O'Rourke
Common Edge-Unzippings For Tetrahedra, Joseph O'Rourke
Computer Science: Faculty Publications
It is shown that there are examples of distinct polyhedra, each with a Hamiltonian path of edges, which when cut, unfolds the surfaces to a common net. In particular, it is established for infinite classes of triples of tetrahedra.
Continuous Blooming Of Convex Polyhedra, Erik D. Demaine, Martin L. Demaine, Vi Hart, Joan Iacono, Stefan Langerman, Joseph O'Rourke
Continuous Blooming Of Convex Polyhedra, Erik D. Demaine, Martin L. Demaine, Vi Hart, Joan Iacono, Stefan Langerman, Joseph O'Rourke
Computer Science: Faculty Publications
We construct the first two continuous bloomings of all convex polyhedra. First, the source unfolding can be continuously bloomed. Second, any unfolding of a convex polyhedron can be refined (further cut, by a linear number of cuts) to have a continuous blooming.
Conical Existence Of Closed Curves On Convex Polyhedra, Joseph O'Rourke, Costin Vîlcu
Conical Existence Of Closed Curves On Convex Polyhedra, Joseph O'Rourke, Costin Vîlcu
Computer Science: Faculty Publications
Let C be a simple, closed, directed curve on the surface of a convex polyhedron P. We identify several classes of curves C that "live on a cone," in the sense that C and a neighborhood to one side may be isometrically embedded on the surface of a cone Lambda, with the apex a of Lambda enclosed inside (the image of) C; we also prove that each point of C is "visible to" a. In particular, we obtain that these curves have non-self-intersecting developments in the plane. Moreover, the curves we identify that live on cones to both sides support …
Convex Polyhedra Realizing Given Face Areas, Joseph O'Rourke
Convex Polyhedra Realizing Given Face Areas, Joseph O'Rourke
Computer Science: Faculty Publications
Given n ≥ 4 positive real numbers, we prove in this note that they are the face areas of a convex polyhedron if and only if the largest number is not more than the sum of the others.
A Note On Solid Coloring Of Pure Simplicial Complexes, Joseph O'Rourke
A Note On Solid Coloring Of Pure Simplicial Complexes, Joseph O'Rourke
Computer Science: Faculty Publications
We establish a simple generalization of a known result in the plane. The simplices in any pure simplicial complex in Rd may be colored with d+1 colors so that no two simplices that share a (d-1)-facet have the same color. In R2 this says that any planar map all of whose faces are triangles may be 3-colored, and in R3 it says that tetrahedra in a collection may be "solid 4-colored" so that no two glued face-to-face receive the same color.
Slider-Pinning Rigidity: A Maxwell-Laman-Type Theorem, Ileana Streinu, Louis Theran
Slider-Pinning Rigidity: A Maxwell-Laman-Type Theorem, Ileana Streinu, Louis Theran
Computer Science: Faculty Publications
We define and study slider-pinning rigidity, giving a complete combinatorial characterization. This is done via direction-slider networks, which are a generalization of Whiteley’s direction networks.
Sparse Hypergraphs And Pebble Game Algorithms, Ileana Streinu, Louis Theran
Sparse Hypergraphs And Pebble Game Algorithms, Ileana Streinu, Louis Theran
Computer Science: Faculty Publications
A hypergraph G=(V,E) is (k,ℓ)-sparse if no subset V′⊂V spans more than k|V′|−ℓ hyperedges. We characterize (k,ℓ)-sparse hypergraphs in terms of graph theoretic, matroidal and algorithmic properties. We extend several well-known theorems of Haas, Lovász, Nash-Williams, Tutte, and White and Whiteley, linking arboricity of graphs to certain counts on the number of edges. We also address the problem of finding lower-dimensional representations of sparse hypergraphs, and identify a critical behavior in terms of the sparsity parameters k and ℓ. Our constructions extend the pebble games of Lee and Streinu [A. Lee, I. Streinu, Pebble game algorithms …
Some Properties Of Yao Y4 Subgraphs, Joseph O'Rourke
Some Properties Of Yao Y4 Subgraphs, Joseph O'Rourke
Computer Science: Faculty Publications
The Yao graph for k = 4, Y4, is naturally partitioned into four subgraphs, one per quadrant. We show that the subgraphs for one quadrant differ from the subgraphs for two adjacent quadrants in three properties: planarity, connectedness, and whether the directed graphs are spanners.
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.