Big batch o' papers

Just uploaded four newish papers to arxiv. They are:

• The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data (with Mike Goodrich and Jonathan Sun, from SoCG'05). Random sampling gives an efficient way of dynamizing quadtrees and performing approximate range queries with them.

• Skip-Webs: Efficient Distributed Data Structures for Multi-Dimensional Data Sets (with Lars Arge and Mike Goodrich, from PODC'05). Distributed versions of tries, skip quadtrees, trapezoidal decompositions, etc.

• Confluent Layered Drawings (with Mike Goodrich and Jeremy Meng, from Graph Drawing '04). A combination of our confluent drawing idea from GD'03 with Sugiyama style layered drawings. This is the paper that the leaning tower of Pisa logo (at right) for SoCG'05 came from.

• Nonrepetitive Paths and Cycles in Graphs with Application to Sudoku. A combination of graph algorithms and rule-based puzzle solving heuristics. I still need to figure out where to send this, maybe another combinatorial games workshop of some sort?

I also heard this week that another confluent drawing paper with Goodrich, Meng, and myself has gotten into GD'05. Good news, because that means Jeremy has enough publications to put together a very coherent thesis. Will upload after responding to referee suggestions.