Louis Theran

most citedSparse Hypergraphs and Pebble Game Algorithms

1 citations · 2 across the 3 of their papers we have counts for

collaborators

Showing math.COShow all

4 papers · 1 filter

math.CO2011★ 1 cited

Lines induced by bichromatic point sets

Louis Theran

An important theorem of Beck says that any point set in the Euclidean plane is either ``nearly general position'' or ``nearly collinear'': there is a constant C>0 such that, given…

math.CO2008★ 1 cited

Rigid Components of Random Graphs

Louis Theran

The planar rigidity problem asks, given a set of m pairwise distances among a set P of n unknown points, whether it is possible to reconstruct P, up to a finite set of possibilitie…

math.CO2007

Sparsity-certifying Graph Decompositions

Ileana Streinu, Louis Theran

We describe a new algorithm, the $(k, ℓ)$ -pebble game with colors, and use it obtain a characterization of the family of $(k, ℓ)$ -sparse graphs and algorithmic solutions to a f…

math.CO2007★ 1 cited

Sparse Hypergraphs and Pebble Game Algorithms

Ileana Streinu, Louis Theran

A hypergraph $G = (V, E)$ is $(k, ℓ)$ -sparse if no subset $V^{'} \subset V$ spans more than $k ∣ V^{'} ∣ - ℓ$ hyperedges. We characterize $(k, ℓ)$ -sparse hypergraphs in terms of graph theo…