Erin Wolf Chambers and I had a paper accepted yesterday to the journal Discrete & Computational Geometry, a journal I now highly recommend.  This entry is a story about that paper as well as the journal.

In a keynote talk at CanaDAM 2011, Stéphan Thomassé referred to the following theorem of Chepoi, Estellon and Vaxès:

Any planar graph of diameter at most 2R has a subset of O(1) vertices such that every vertex in the graph is within distance R of that subset.

We’ll call this coverage of the graph by O(1) balls of radius R the “ball-coverage property”.  The proof is quite deep in that it calls on the fractional-Helly property of the set system of radius-R balls.  In his talk, Thomassé states that the constant is not computed in the paper, but was done so by a student.  I don’t remember the exact number, but it was around 800.

Surely that can’t be the right number.  I worked for a while on coming up with a different, more direct proof that would result in a better number.  Something reasonable.  Like 5.  Or 7.  The best known lower bound is 4.

I haven’t been successful.  Erin and I, in our first successful collaboration which involved an allergic reaction to St. Louis (actually to a hand cream, not St. Louis), generalized the result to bounded genus graphs.  That is this paper.  We thought we had it generalized to clique sums of surface embedded graphs … we can handle apices, but vortices and clique sums proved … tricky.  As they seem to be.  But I would suggest that minor-excluded graph families have the ball-coverage property.

We had this result written up in the summer and debated where to send it.  SoCG was out as Erin is on the PC this year.  Rather than wait for a spring submission, we decided to go straight for a journal.  We submitted to DCG on October 22, 2013.  We were asked for what turned out to be minor revisions on March 12, 2014 and resubmitted on March 19.  The final acceptance came in on March 31, 2013.  Just over 5 months from first submission to acceptance.

That is comparable to the roughly 3 months for conferences, with the added benefit that you can actually have a back-and-forth as needed with the reviewers through the editor.  No rejections based on misunderstandings.  No rejections based on “we only have X spots”.  No rolling the dice.  And no travel to yet another far away conference.

If only more journals were like this.  If only conferences were more about giving a place for people to meet (regionally as well as internationally) and less about picking the X top papers without a truly full review even though it is treated like a fully published result … well … that would be great.