Two papers my coauthors and I recently uploaded to the arXiv:

Succinct Greedy Graph Drawing in the Hyperbolic Plane, with Mike Goodrich. A drawing is greedy if a greedy routing algorithm (in which messages are passed to any neighbor who is closer to the final destination) succeeds in getting messages from any source to any destination. It's recently become fashionable to study embeddings of this type; Papadimitriou conjectured that all planar graphs have greedy drawings in the Euclidean plane while Bobby Kleinberg showed that all graphs, regardless of planarity, have greedy drawings in the hyperbolic plane. In Euclidean geometry of any bounded dimension, though, not all graphs can be greedily embedded: a star with enough leaves provides a counterexample. The supposed motivation for all of this is to assign artificial coordinates to nodes in an ad-hoc wireless communication network and let them use greedy routing to communicate with each other, but my general feeling is that a lot of the researchers in this area have lost sight of that goal: when their embedding schemes are analyzed in terms of the bit complexity of their coordinates, they're more expensive than just storing a complete routing table that ignores any geometry. Our result is that one can implement a Kleinberg-like embedding of any graph into the hyperbolic plane while using only logarithmically many bits to represent the coordinates of each node. More, it's easy to compare distances in our coordinate scheme without having to know any hyperbolic geometry. So, it's possible to devise a routing scheme that is practical, implementable, and universal, and still stay within this greedy paradigm.

Self-Overlapping Curves Revisited, with Elena Mumford. I think it's easiest to explain this one by a picture:

Bennequin's self-overlapping curve

The curve above is the boundary of a two-dimensional surface, embedded in a self-overlapping way into the plane. What surface? Actually, there are five valid answers. There are two ways of forming a disk with a triangular middle part and three lobes dangling from the middle, and there are also three spirals that start at one of the outer lobes and wind around the three loops until they end at another outer lobe. All five have this curve as their boundary. Each of the three spirals can be embedded as disks into three dimensions so that they don't self-intersect and, when projected back to the plane, still have this boundary. The two three-lobed surfaces, on the other hand, have no such 3d embedding: the three lobes get in each other's way. Try making it out of paper by cutting out several copies of this image and taping them together if you don't believe me. The 2d version of the problem goes back to Whitney in 1937, and was studied algorithmically by Shor and van Wyk in the first SoCG; we study algorithmic versions of the 3d problem and show that subtle differences in the problem statement can make a big difference in its complexity.