I was interested to see two new preprints show up this evening that both used very similar ideas to solve quite different problems in geometric graph algorithms.

Knauer and Werner's "Erdős-Szekeres and Testing Weak epsilon-Nets are NP-hard in 3 dimensions - and what now?" (arXiv:1111.5979) proves, among other things, that it's NP-hard to find the largest subset of points, from a set of n points in three dimensions, that form the vertices of an empty polyhedron. A two-dimensional version of the problem can be solved in polynomial time. Knauer and Werner prove that the three dimensional problem is hard by a reduction from the maximum independent set problem in certain planar graphs, the coin graphs determined by sets of non-overlapping unit disks in the plane, with a vertex for each disk and an edge connecting each two touching disks. They lift the centers of the disks to points on a convex surface in 3d, and add extra points near the lifted images of the tangency points, in such a way that the largest convex subset of the lifted set consists of all the extra points together with maximum independent subset of the lifted coin graph vertices. Since maximum independent sets of unit-radius coin graphs are hard to find, so are maximum convex sets in 3d.

Cabello, Cardinal, and Langerman's "The Clique Problem in Ray Intersection Graphs" (arXiv:1111.5986) instead looks at the problem of finding a largest mutually-crossing subset of a set of line segments in the plane, or of a set of rays in the plane. Again, they reduce this problem to one of finding the maximum independent set in a planar graph. If the edges of a planar graph are replaced by paths of odd length, the subdivision changes the independent set in a predictable way (it increases by half the number of added vertices), and Cabello et al show that it is possible to do this subdivision in such a way that the complement of the graph can be represented by the intersection pattern of a set of rays: that is, the vertices of the subdivided planar graph correspond to rays in the plane in such a way that two vertices are adjacent exactly when the corresponding two rays are disjoint from each other. Conversely, a set of rays is mutually crossing if and only if it corresponds to an independent set in the planar graph. Since finding maximum independent sets of subdivided planar graphs is hard, so is finding largest sets of non-crossing rays.