I've uploaded another WADS paper to the arxiv today: Orientation-Constrained Rectangular Layouts (with Elena Mumford, arXiv:0904.4312). It's a follow-up to our paper to appear at SoCG on rectangular cartograms, stylized maps in which countries or other regions are replaced by rectangles whose areas represent numerical quantities associated with the regions. In the SoCG paper, we were concerned about area-universality, the ability to morph a cartogram from any set of areas to any other set without changing the orientations of the rectangles, but here we're concerned about a more basic question: which sets of orientations are possible? If, say, I wanted to draw a cartogram for the counties of southern California, it would help readers understand which rectangle corresponds to which county if they could be placed in something resembling their geographic arrangement. For instance, Los Angeles County should be placed above (to the north of) Orange County, or at least not directly below it where San Diego County should be.

( Read more... )

Below are links to a couple of interesting-looking recent arXiv preprints.

( Very large graphs )

( Kepler conjecture )

In other news, I visited Harvard last week for the STOC PC meeting; see Michael Mitzenmacher's long series of blog posts about the program committee meeting and the reviewing process for some flavor of what that was like. Or if'd rather just look at some pretty geometric pictures and movies, how about myriahedral projections, Jack van Wijk's unfoldings of the earth's surface (via MF).

In recent years on the web we've seen a lot of information visualizations in the form of cartograms, illustrations that resemble maps in that they show regions of the earth but that differ from maps in that the shapes, positions, and adjacencies of these regions are distorted so that their areas represent some non-geographic data to be visualized. A familiar example is the stretched maps of the United States showing the numbers of electoral college votes associated with each state; populous states such as New York and California become larger in these maps while sparsely populated states such as those in the great plains are relatively shrunken.

Although seemingly modern, this kind of visualization goes back at least to a 1934 paper of Erwin Raisz in Geographical Review. ( Read more... )

Another new paper of mine, “Area-Universal Rectangular Layouts,” with Mumford, Speckmann, and Verbeek (my third recent coauthor named Kevin), just appeared on the arXiv. It's about designing cartograms (stylized maps) in such a way that they can be morphed so that their areas represent arbitrary quantitative data about the regions they depict. I'd like to discuss it in more detail soon, but first I wanted to talk about Birkhoff's representation theorem for finite distributive lattices, the subject of a Wikipedia article I worked on recently and a key tool in our rectangular layout paper.

( Read more... )

So last week I attended the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS 2008), which was held here in Irvine. It's a little problematic attending a conference in one's own town — too easy to schedule other conflicting activities — but I still went to much of it, as well as getting some research done with attendee and renaissance man extraordinaire Matt Dickerson (about which more some other time).

( Read more... )

Saw a talk today on how event-based indexing of all multimedia data ever recorded anywhere will save us from the hell that is text documents and searching for keywords on Google. I dunno, I kind of like searching for keywords on Google. I feel I know much more, am much smarter, when I work in combination with Google than on my own. And when I struggle with indexing multimedia data (say, my photos) it's the opposite problem from indexing everything: I want to be selective in what I index, throw away the unimportant photos so they don't distract from the good ones. The talk's claim that photographic data is more objective than text rankled a little as well, since I know from experience that my own photography tends to succeed when I have an emotional response to the subject, and fail otherwise. Even a fully automated webcam is set at a viewpoint which was chosen by a human for a reason, rather than achieving complete objectivity by being completely random and purposeless.

The thought of recording and accessing all human experience as video reminds me of the Borges story of the country where the mapmakers got so good at making maps that they made one at 1:1 scale. Or was it Lafferty? Probably both. Not much use as a map, anyway. And since I like doing Google keyword searches so much: the first Google search I tried finds a bunch of relevant stuff, the sixth hit from which is exactly the quote I wanted:

...In that Empire, the craft of Cartography attained such Perfection that the Map of a Single province covered the space of an entire City, and the Map of the Empire itself an entire Province. In the course of Time, these Extensive maps were found somehow wanting, and so the College of Cartographers evolved a Map of the Empire that was of the same Scale as the Empire and that coincided with it point for point. Less attentive to the Study of Cartography, succeeding Generations came to judge a map of such Magnitude cumbersome, and, not without Irreverence, they abandoned it to the Rigours of sun and Rain. In the western Deserts, tattered Fragments of the Map are still to be found, Sheltering an occasional Beast or beggar; in the whole Nation, no other relic is left of the Discipline of Geography.

Which reminds me, I also kind of like text documents. How could I read Borges without them?

There was some speculation prior to the Graph Drawing Conference, on how many talks into the conference would be the first limerick. Elena Mumford wins, at talk #9, her paper on rectilinear cartograms with Mark de Berg and Bettina Speckmann. Elena may not wish to have her poetry skills memorialized, but here it is:

There was a graph triangulated
whose vertices were heavy weighted.
  So, smart and cruel,
  we chopped its dual.
Cartography is now outdated.

Kurt Mehlhorn also gave a very nice invited talk, with the title changed after the program was printed to something about minimum cycle bases. But really it involved graph drawing: it turns out that there's a nice algorithm for drawing graphs on a torus, similar to Tutte's force-based convex plane embedding, in which we form a linear system of equations by making a variable for each edge (or rather a pair of variables forced to be the negative of each other, one for each orientation of the edge), and require the variables at each vertex and around each face to add to zero. One each of the variable and face constraints are redundant, so (applying Euler's formula to count constraints) this system has two degrees of freedom; that is, all its solutions are the weighted sums of two basic solution vectors. We pick one vertex as a base point at the origin, use one of the solution vectors as the offsets in x coordinate between each pair of adjacent vertices, and use the other solution vector as the offsets in y coordinates. The amazing part is that this works even if you don't know the torus graph you're trying to embed, as long as (1) its facial cycles are all shorter than the torus's nonseparating cycles, and (2) you are given a supergraph of the torus graph, in which the extra edges have endpoints that are connected by paths in the torus graph that are shorter than the torus's nonseparating cycles. You just have to compute a minimum cycle basis of your supergraph, throw away the two long nonseparating cycles, and use constraints for the remaining short cycles in place of the face constraints, and you get the same solution as if you really knew what the faces were. He uses this for solving surface reconstruction problems for toroidal objects, by applying it to a k-nearest-neighbor graph with k chosen large enough that the graph contains a good mesh.

Continuing to go through and clean up some of my old bookmark collections, I found one on cartography and mapmaking. Maps and atlases have always fascinated me, and my son seems to have inherited my interest; in graduate school, I decorated my apartment with maps instead of posters. Nowadays, if I want a quick map of how to get to some location, I tend to go directly to Google Maps, and I've also had fun scanning the satellite imagery there and at TerraServer. Doing an interest search here found cartographica, which looks like it should be fascinating to follow. Here are a few other more specialized mapping sites:

• The Library of Congress Map Room
• The United Nations Cartographic Section
• The Map Room weblog
• Cartogram Central
• Suresh's Election 2004 cartograms

And, just for fun (I think cartome can stand the hotlink):

( New Yorkistan )