My travels (and the lack of decent internet connectivity in Crete) caused me to be remiss in blogging about some future theory events. First, the list of papers to be presented at SODA 2009, in New York City January 4–6 next year, is here. A very welcome innovation this year is the inclusion of abstracts with the titles.

I've already mentioned my accepted paper with Elena Mumford on self-overlapping curves. I also have another one in the list, with Mike Goodrich and Mike's student Darren Strash, “Linear-Time Algorithms for Geometric Graphs with Sublinearly Many Crossings.” The problem concerns the construction of the arrangement of line segments: this can be solved in optimal O(n log n + k) time for n segments with k crossings in the general case, but we were looking for faster algorithms when more about the input is known. Specifically, we assume that the input is a connected graph of line segments for which one already knows the cyclic order of segments around each common endpoint; an important special case of this is dealing with self-crossing polygons. It was already known how to find all crossings in linear time when k is a little bit larger than n; we show the same thing when k is a little bit smaller than n. The case where both numbers are the same order of magnitude remains open. We should have a preprint version ready in a few days.

Finally, the call for papers for SoCG 2009, to be held in Aarhus, Denmark, June 8–10, is out. Titles and abstracts are due by November 24, with the actual submission deadline December 1.

I'm back from Graph Drawing 2008 in Crete, and too jet-lagged to blog coherently about it, other than to say that on the whole it went well -- interesting talks, too much tasty seafood and raki (though the lack of beverages at the lunches, similarly to WADS 07, was a minor annoyance), a spectacular location (which I somehow failed to take any photos of, but there should eventually be plenty of others on the conference site), good company, and even some progress on the research problems I was thinking about during the conference.

My own talk slides are now online: The topology of bendless three-dimensional orthogonal graph drawing and Isometric diamond subgraphs.

This week, I'm in Karlsruhe (again), where I've been attending the European Symposium on Algorithms and the associated workshops of ALGO 2008.

( Read more... )

The list of accepted papers for ACM GIS 2008 (to be held this November in Irvine) is out, and there's a lot there that looks of likely interest to computational geometers.

My own contribution with Mike Goodrich is Studying (Non-Planar) Road Networks Through an Algorithmic Lens. The technical content of the paper concerns using separator decompositions and various related tricks to speed up algorithms for network optimizations such as shortest paths (allowing arbitrary edge weights, as needed to model user preferences for trading off speed, distance, toll cost, scenicness, etc.) but the main point of the paper is to point out that real-world road networks are far from the planar graphs they are often erroneously assumed to be, and to attempt to model them more accurately as subgraphs of low-ply disk intersection systems building on Shang-Hua Teng's neighborhood graph research.

The list of Graph Drawing 2008 accepted papers is out.

Unlike some larger theory conferences, Graph Drawing allows program committee members to submit papers (but not to see or contribute to the deliberations on their own submissions) because otherwise it would be difficult to field a program committee without cutting off a large fraction of the conference's contributors. Therefore, although I was on the PC, I also have some papers in the list: two on xyz graphs and greedy embedding that I've already discussed here, and one additional short paper, “Isometric Diamond Subgraphs.” I don't want to spend a lot more space describing this last one, but let me just show a couple pretty pictures.

( Read more... )

There's plenty of other interesting research to be presented at the conference, so come to Crete and find out all about it!

Usually when I put up a new preprint on my web site or the arXiv, I'll mention it here, but today I'm instead going to plug two of my papers that I haven't yet put on my web site. They're both ones that have appeared in print recently, though. Both are the results of some quadrilateral meshing research that I did a year ago with Mike Goodrich, Ethan Kim, and Rasmus Tamstorf, while Mike and I were consulting for Disney Feature Animation and Ethan (a student of Sue Whitesides at McGill) was interning there.

( Read more... )

Via Muthu: the list of papers accepted to FOCS 2008 is out.

In the comments to this post, John Sidles examines seven dirty words of theory, and whether their presence in the title of a paper is a detriment to its acceptance chances. Fortunately, “algorithm” doesn't seem to fit as one of them...

Did you hope to go to Graph Drawing 2008 in Crete, but didn't have time to finish writing up that submission before the deadline this Saturday? Now you still have a chance. I've just received word that the conference submission deadline has been extended, to Thursday June 5, 2008 (noon Central European Time). Submission types include long papers (12 pages), short papers (6 pages), demos, and posters (2 page description required); see the call for papers for details.

In other algorithm conference news, via Muthu, the list of ESA accepted papers (including mine with Barequet, Goodrich, and Vaxman on 3d straight skeletons) is out.

And in other other algorithm news, congratulations to Shang-Hua Teng and Dan Spielman for winning the Gödel prize for their work on smoothed analysis of linear programming!

Via Mihai, who in turn got it from Joachim: the Scandinavian Workshop on Algorithm Theory (SWAT) acceptances. In other news, Joachim G. has a blog. You'd think "Joachim G." would be sufficient to identify a theorist uniquely, wouldn't you? But no, this is Joachim Gudmundsson, not Joachim Giesen.

And via Michael M.: the ICALP track A (algorithms and theory) acceptances.

Mihai also has an accurate description (from his point of view on the SWAT committee) of how the ICALP committee worked. Leslie Goldberg did a great job of making it run smoothly, though, and I think we made a good set of decisions.

I got some good news last week: one of my papers was accepted to Shape Modeling International. But that was tempered by some very bad news today, as all of my submissions to the Symposium on Computational Geometry were rejected (0 for 5!). See the accepted paper list, e.g., here. I suppose that at least simplifies my travel plans and improves my ability to afford to travel to Graph Drawing later this summer...

( Roundup of the rejects )

I realize it's not exactly day 3 anymore, and it's all a bit of a blur by now, but I thought I'd finish my reporting of the conference regardless. Besides, my flight is delayed so I have plenty of time to write, I'm procrastinating on making slides for my next talk, and it's a good excuse to plug my SODA talk slides and my book, especially since Springer mysteriously failed to do the latter at their exhibit table.

( Read more... )

For more on ALENEX/ANALCO and SODA, see my previous entries (I, II, III), Suresh's (I, II, III), Michael Mitzenmacher (I, II), and Hal Daume.

Let me explain... no, there is too much. Let me sum up.

( Read more... )

My iPod's randomizer this morning decided to treat me to some Metasciences and Casiotone for the Painfully Alone. All it needed, I thought, was some Say Hi To Your Mom (of which I have plenty) for the nerdy music trifecta to be completed. So I was looking forward to tonight's concert by Lady X and the Positive Eigenvalues, Christos Papadimitriou's band, for another hit of nerdy music. My (excellent) dinner ran long, though, sadly, so I had to miss it. I hope those who attended had a good nerdy time.

( Some of the talks )

My usual pattern here is to start with high hopes of several long complicated blog posts, and then get more terse and less frequent as the conferences go on and I get more sleep-deprived. So don't count on this continuing...

( Read more... )

I tried making my hotel reservation for ALENEX and SODA today, only to be told that not only is the SODA block of rooms at that hotel sold out, but the hotel itself is booked full, and the nearest hotel the reservation agent could suggest was a mile away. It seems strange to me that this would happen nearly four weeks before the supposed deadline, but anyway. Is anyone else in this predicament? What other hotels in the area (near Van Ness and Geary in San Francisco) can anyone suggest?

ETA: Google maps to the rescue. I ended up choosing the Carlton, only 1/4 mile away, for around 80% of the conference rate for the Holiday Inn. Looks like there are several other choices within a similar distance and price range.

ETA2: According to David Johnson, the hotel does still have rooms, but you have to call the 415 number instead of the 800 number to get them.

TGGT 2008, a conference on topological and geometric graph theory, will be held May 19-23, 2008, in Paris, dedicated to Hubert de Fraysseix on his 60th birthday. The call for papers just came out; submissions are due by the end of this year.

Phil Klein asked me to post that the hotel for FOCS 2007 has extended its deadline for booking at the conference rate through September 23. He says that rooms are scarce in Providence for the Saturday night before FOCS (October 20), so if you hope to go to FOCS and haven't already done so you should reserve a room immediately.

Via Muthu: the list of accepted papers at the 2008 ACM-SIAM Symposium on Discrete Algorithms (SODA) is now available.

I'm happy to report that my own submission, the one on recognizing partial cubes, is among the accepts. So I'll see you all in San Francisco!

Ileana Streinu is running a discussion of how she thinks theory conference reviewing procedures could be improved on a new blog. It's mostly centered around SoCG, but could be of interest to other similarly-run conferences.

It seems like a good thing, in general, to discuss our procedures, identify what problems they may be causing, and work towards improving them with a careful analysis of the advantages and disadvantages of proposed changes. But I'm a little uncomfortable with the "subsequent vote" part of the proposed events there. The subset of the SoCG community that participates in SoCG business meetings is small and self-selected, true, but even more so is the subset of the SoCG community that participates in blogs, and I'm not confident in the disinterestedness of the moderator. Isn't that what we have a steering committee for?

ETA: Sariel is also skeptical. And MM argues that the benefits of PC meetings are outweighed by the costs.

The list of papers accepted to the 2007 European Symposium on Algorithms, to be held in October in Eilat, Israel.

The paper of Ausiello et al on streaming spanners (or at least, its title) looks especially interesting to me.