In the updated version of my previous post, I mentioned nine potentially-minimal forbidden minors for the apex graphs: the seven graphs of the Petersen family, a cube with two doubled vertices, and the double pyramid over a triangular prism.

Unless I've made a mistake in my calculations (entirely likely), the following nine graphs are also minimal forbidden minors for the apex graphs:



In addition, the three components in the three graphs on the right can be mixed and matched, leading to another ten combinations not shown. With the number of obstacles growing to at least 28, my hope for a clean characterization is diminishing.

ETA: Still another one: start with a cube, find a four-vertex independent set, and make three copies of each of its vertices. The resulting 16-vertex graph has four K_3,3 subgraphs, one for each tripled vertex.

I've been reading about YΔY-reducibility today. A connected graph is YΔY-reducible if it can be reduced to a single vertex by YΔ and ΔY transformations (replace a triangle by a degree-three vertex or vice versa) and series-parallel reductions (remove self-loops and multiple adjacencies, delete degree-one vertices, and contract paths of degree-two vertices into single edges). Every planar graph is reducible; it makes an amusing exercise to transform your favorite planar graph (such as a cube) into nothing, using these operations.

( Read more... )

ETA 7/25: Here's another forbidden minor for the apex graphs. Start with a triangular prism, and connect two new vertices to each of the six prism vertices but not to each other. It's the graph of a 4-polytope, the double pyramid over the prism. It's also a YΔ transformation of an apex graph, but not itself an apex graph.

The list of accepted papers to Graph Drawing 2010 is out. I'm not yet sure whether abstracts will be available as well sometime soon, but I hope so.

I have several papers on the list that I'll post about in more detail once we have time to handle the reviewers' suggestions and make preprints available. What I do have ready to post today, though, is some software from one of the papers.

In case you haven't already seen his work, Mark Lombardi was an artist whose art consisted of graph drawings of social networks describing the connections among members of crime syndicates, international financiers, and high politicians. Unlike in a lot of other graph drawings, Lombardi's art generally depicts graph edges as curved arcs, and he obviously put a lot of care into the rhythm and spacing of the vertices. I and my co-authors were inspired by his works to define "Lombardi drawings" to have a more technical sense: drawings in which all edges are arcs of circles and in which the angles of the edges are equally spaced around each vertex. Two of our papers at GD will be on this subject.

As part of our investigations into these kinds of drawings, I wrote a program, which I call the "Lombardi Spirograph", to create them, and have put it online as LombardiSpirograph.py (see the program for usage hints). It works for graphs that can be drawn with the vertices in concentric circles, with all vertices on the same circle having the same pattern of connections, which is enough to cover many of the most famous named graphs. Here are a few of its drawings, of the Grötzsch graph, Nauru graph, Dyck graph, and the 40-vertex cubic symmetric graph.

Somehow this quote reminded me of what it's like to work on Wikipedia:

For all their seeming kinship, a restorer is the antithesis of a painter: he is a conserver, not a creator. Like a mimic, he assumes another person’s style, at the expense of his own identity. He must resist any urge to improve, to experiment, to show off; otherwise, he becomes a forger. Yet, unlike a great actor, he receives no glory for his feats of mimicry. If he has succeeded, he has burnished another artist’s reputation, and vanished without the world ever knowing who he is, or what he has accomplished. The art historian Max J. Friedländer called the business of the restorer “the most thankless one imaginable.”

(The New Yorker story it's from is about the problem of matching artworks to their authors, and is well worth reading in full.)

Speaking of Wikipedia, I've put together a collection of Wikipedia articles on graph algorithms. You can print it (though I'm not sure why you would want to), download it as a pdf, or just use it as a convenient set of links. I'm not really satisfied with the texts I've seen on the subject, though there are plenty on graph theory, and some good ones on more specialized topics such as network flow or graph drawing. So last quarter when I taught an undergraduate elective on graph algorithms, I used Wikipedia for most of my readings, with some other links filling in the gaps in its coverage. The new collection is aimed at sharing that experience and allowing others to use it in the same way.

It's the latest trend. How can I resist making a small contribution?



Unrelatedly, you know that problem at receptions where holding a plate of hors d'oeuvres in one hand and a wine glass on the other means you don't have a free hand to eat your food with? Solved!

Families of graphs that are closed under the operation of taking minors have a deep and mysterious structure theory, in which the graphs in the family can be formed by clique-sums of bounded-genus graphs with finitely many "apexes" and "whorls". But in some cases, the structure can be greatly simplified: if one of the forbidden minors of the family can be drawn in the plane with only one crossing, then the graphs in the family can be formed from clique-sums that only involve planar graphs and constant-sized graphs.

For instance, the K₅-free graphs are formed by gluing together planar graphs and copies of the eight-vertex Wagner graph at their vertices, edges, or triangles. A similar decomposition is known for the K_3,3-free graphs, with K₅ taking the place of the Wagner graph.

We know how to solve the maximum flow problem in planar graphs quite efficiently, in part because it's closely related through planar graph duality to easier shortest path problems. For instance, Borradaile and Klein (JACM 2009) showed how to solve planar directed flow problems in O(n log n) time. It would be nice if we could extend these speedups to broader classes of graphs. Some such extensions are known: Chambers, Erickson, and Nayyeri, in two papers at SoCG'09 and STOC'09, found efficient algorithms for flow problems in bounded genus graphs, and Hochstein and Weihe at SODA'07 showed how to solve flows efficiently for graphs that can be drawn in the plane with a bounded number of crossings. But none of these techniques seemed to extend to more general minor-closed families.

My new preprint with Erin Chambers, "Flows in One-Crossing-Minor-Free Graphs" (arXiv:1007.1484) extends the planar flow algorithms in a different direction, to one-crossing-minor-free graphs. The basic idea is to apply a technique from Hagerup, Katajainen, Nishimura, and Ragde (JCSS 1998) for flows in graphs of bounded treewidth. Bounded-treewidth graphs are, essentially, the graphs that you get from clique-sums of constant-sized graphs, and the idea of Hagerup et al. is to repeatedly replace the subgraph on one side of a clique-sum by a constant-sized "mimicking network" with the same flow properties. With some care in how the replacements are ordered and in the construction of the mimicking networks, the same idea turns out to work for the clique-sums in the structural decomposition of one-crossing-minor-free graphs. The Hochstein-Weihe result also comes into play, because as the sequence of replacements progresses we need to compute flows in planar graphs with constant-sized replacement graphs glued into them, which are a special case of graphs with a constant number of crossings.

The real goal is to handle arbitrary minor-closed graph families, but to do that we'd need to extend our techniques in three ways: we need to handle clique-sums of bounded-genus but nonplanar graphs, we need to handle apexes, and we need to handle whorls. There are some technical reasons why our methods don't immediately extend to the bounded genus case, involving the possibility that the triangles that components of a clique-sum are glued together along might not be separating. And since whorls involve bounded pathwidth there's some hope of progress there. But the apexes seem to be a problem. A single apex can introduce an unbounded number of crossings. And, even finding maximum flows in planar graphs with apexes, without all the other aspects of the structure theory, would be interesting: it would allow us to solve planar problems with multiple sources and multiple sinks, by connecting all these terminals together to new apex nodes.

This past week we went on a little family vacation to Avalon, an hour's boat ride offshore from us on Catalina Island. Here are some photos, including many of the distinctive tilework that decorates the town.

The FOCS accepted abstracts are out and Kintali has pointers to online copies of the papers. A few that caught my attention:

• A non-linear lower bound for planar epsilon-nets, Alon. If S is a set of points in some geometric space, and R is a set of shapes (e.g. all possible axis-aligned rectangles in the plane), then an ε-net is a subset of S that hits every "large" shape, where a shape is large if it includes an ε fraction of S. These things are very useful in making geometric algorithms deterministic, because they can often be used in place of random samples from S. The size of an ε-net turns out to depend only on ε and not on S: a general upper bound shows that for many reasonable sets of shapes, this size is O(1/ε log 1/ε) but in a few cases better bounds of the form O(1/ε) were known. This paper shows that such good bounds cannot hold more generally.

• Subcubic equivalences between path, matrix, and triangle problems, Williams and Williams. Although there are fast matrix multiplication based techniques that work well for graphs with small integer weights, for decades there hasn't seemed to be anything much better than cubic time in the worst case for all pairs shortest path problems on arbitrarily weighted directed graphs. This paper shows that there is a collection of many path problems including APSP that are all stuck in the same boat: an improvement to one of them would improve the rest as well. The problems include negative cycle detection, finding triangles, and the k-shortest simple paths problem (even in the special case k = 2).

• On the queue number of planar graphs, Di Battista, Frati, and Pach. Suppose that we maintain a set of k queue data structures and, at each of n time steps, perform some number of enqueue and dequeue operations on distinct items. Draw a graph that has the time steps as vertices and that has an edge between the enqueue time and the dequeue time of each item. Then this graph has queue number k. The stack number can be defined analogously, and is the same as the pagenumber or book thickness; it's known that planar graphs have pagenumber at most 4. This paper shows that the planar graphs also have polylogarithmic queue number, and they use this result to find low-volume 3d grid embeddings in which no two edges intersect. It's unusual to see graph drawing research in FOCS but this looks like a nice result.

I just uploaded another paper to arxiv, "Regular Labelings and Geometric Structures", arXiv:1007.0221. It's a survey about some unexpected similarities between lattice embeddings of planar graphs, partitions of rectangles into smaller rectangles, and orthogonal polyhedra. All of these things can be described combinatorially by a "regular labeling" consisting of a coloring and orientation of an associated maximal planar (or nearly maximal planar) graph. All of these regular labelings have local constraints at what the labeling can look like near a vertex, and in all of them these local constraints force certain subgraphs formed by edges of one or two colors to be acyclic. In all three cases there are simple characterizations of the graphs that support a labeling, that lead to efficient algorithms for constructing the objects described by the labeling. And in all three cases the possible labelings of a fixed graph form a distributive lattice in which adjacent labelings differ from each other by a local twist operation. I don't really understand why these things should act so similarly to each other and in part I wrote this as a request for a better explanation. But it's also a teaser for my invited talk at CCCG this summer, at which I plan to talk about this material in a little more detail.

On a related note, the slides from my coauthor Elena Mumford's talk on orthogonal polyhedra at SoCG last month are now online.

I don't have to list all the reasons why it's important to find all the maximal cliques in a graph, I think, but I heard a new one today (a form of social network analysis): one of the lecturers in my department wants to find cliques in a graph representing similarities between homework assignments of different students in the same class. You can guess why...

Anyway, I have a new preprint out with Maarten Löffler and Darren Strash on exactly this problem: "Listing All Maximal Cliques in Sparse Graphs in Near-optimal Time", arXiv:1006.5440. The main piece of background for our paper is the Bron–Kerbosch algorithm, a simple recursive backtracking procedure for listing all maximal cliques which works well in practice but which has only limited theoretical bounds on its performance. As the original Bron & Kerbosch paper already observed, a strategy known as "pivoting" helps to control the number of recursive calls at each step of the algorithm, and Tomita, Tanaka, and Takahashi showed that with careful choices of pivots the algorithm could be made to run in time at most equal to the worst-case bound on the number of maximal cliques in an n-node graph, 3^n/3.

The new paper suggests a different strategy for improving the running time of the Bron–Kerbosch algorithm: choose the order of the recursive calls carefully. In particular it works well (according to our analysis) to add vertices to a partial clique in order by their degrees: first try adding the vertex with the smallest degree, second try the vertex whose degree in the remaining subgraph is smallest, etc. Doing this at the top level of the recursion (without pivoting), and then switching to the Tomita et al. pivoting strategy at lower levels, leads to a time bound that is linear in any sparse family of graphs (such as the planar graphs) and that has near-optimal dependence on the degeneracy of the graph, a standard measure of its sparseness.

The modified version of the Bron–Kerbosch algorithm is still very simple, and (we hope) practical, but we have not yet had a chance to perform any experimental tests to determine how much the vertex ordering helps the algorithm in practice.

It's been a while since I've taken much sports/action photography, but they were having belt tests at my son's aikido dojo, so... Photos.

A few photos from my recent visit to Snowbird. Obviously, I fail at capturing any of the action of the conferences themselves.

Two of the shots may need a little explanation. The one below is the Cliff Lodge, the hotel where many of us stayed, reflecting the hillside from which the view was taken; my own reflection is hidden behind the tip of the flag. This other one was painted on the side of a truck, parked near Ichiban Sushi in Salt Lake City; I never managed to determine whether it was graffiti or intentional decoration by the truck owner.

I spent much of the past week in Snowbird, Utah, for the annual Symposium on Computational Geometry and its satellite Workshop on Massive Data Algorithmics. A random selection of SoCG highlights (with apologies to anyone whose research I'm misrepresenting or omitting):

( Read more... )

Although the talks at Massive covered algorithms for a wide range of specific problems, the overall focus seemed to me to be less about solving problems and more about exploring model space. Along with the by-now traditional work on cached external memory models and streaming algorithms, two newer models struck me as particularly interesting:

( Read more... )

Snowbird itself was a pleasant place to visit. Although the timing was awkwardly placed between their winter and summer seasons (the ski runs had just shut down and the luge run was still being set up) the weather cooperated for the hiking break on Tuesday and on the next night I had the unexpected pleasure of being snowed on in a hot tub in June. The restaurant selection was a little slim but some of the local choices were pretty good (my favorites: the Fork Lift for breakfast and the Steak Pit for dinner) and with a rental car the whole of Salt Lake was within easy reach. And (except for a brief resort-wide power outage on the last day) the internet connectivity was as good as I can remember at any conference.

Some other SoCG/Massive reports: Sariel, Sorelle, Sorelle, Sorelle, and Suresh. It's enough to make me want to change my name to something starting with S[vowel]R, or to encourage Sergio and Sergei to start blogging.

It's the end of the school year, and that means end-of-year performances, and that means photos of end-of-year performances. My son's elementary school music concert and my daughter's drama class performance, to be more specific. The drama (a sequence of scenes from Little Women) was enlivened by the way it was set, with the girls trading roles according to which accessories they were wearing.

The drama scenes are the first photos I've processed after upgrading to Adobe Photoshop CS4 (I bought the upgrade just a little too soon to get CS5) and it seems to be working really well. It is fast, it doesn't need a separate conversion program to handle my camera's raw files, and it produces excellent results with very little adjustment needed even in difficult conditions (stage lighting with no flash, and the camera's ISO set to the maximum). I've also been using the CS4 version of Illustrator for a few weeks now and I like the changes I've noticed (easier alignment of objects and easier adjustment of the drawing board size, mostly).

I have another new preprint on arXiv, Cloning Voronoi Diagrams via Retroactive Data Structures (with Matt Dickerson and Mike Goodrich), my contribution to the recent set of papers accepted to ESA 2010. (And where are the abstracts for this list of accepted papers, anyway?)

The basic scenario for our paper is something like this: you work for Starbucks, and would like to provide your customers with a web service in which they can look up the location of the Starbucks cafe nearest them. But, you don't want to make it easy for your competitors to use the service to build up a complete database of all your cafe locations. What can you do?

( Read more... )

Yes, there's graffiti in Irvine, it's just a little harder to find than in some other places. But the directions that I found on the web were accurate, and led me to a storm sewer under UCI that's filled with art. Photo gallery here.

Also, if you have any interest in street art, you need to see Exit Through the Gift Shop. It's still playing at the local art house movie theater here, a short walk from of all this graffiti. Whether it's all true, an elaborate send-up, or both, it's very entertaining.

Most versions I've seen of the planar separator theorem give the primary role to the separator and the vertices: a separator is a small set of vertices the removal of which splits the remaining vertices into two subsets of roughly equal size. But when one states it in this way, one actually ends up with three parts (the separator vertices themselves form the third part). How the removal splits the remaining vertices is somewhat unclear, because it's not just into connected components: one may get more than two connected components and then have to regroup them to form the two sides of the split. And there's some ambiguity about where the edges go: all edges incident to the separator are deleted? We group the edges into five different sets according to which one or two vertex subsets they touch?

I think it makes things simpler to put the edges and the split first: a separation is a partition of the edges of the graph into subgraphs. Once you have that part clear, the separator is easy to find: it's just the set of vertices that appear in more than one subgraph of the separation. So the planar separator theorem, rephrased in this way, states that the edges of any planar graph can be partitioned into two subgraphs, with each subgraph having at least n/3 vertices and with O(√n) shared vertices.

(Why "at least n/3" rather than "at most 2n/3"? Because it matches more closely the "at most 2n/3" in the usual statement of the separator theorem in which the separator vertices are not counted towards either side. And because it's not true otherwise unless you change it to 2n/3 + O(√n) or make things messier by adding "for all sufficiently large n". Consider K₄: its edges have no partition into two subgraphs with fewer than four vertices in the larger one.)

It's not a big deal; I don't think it makes a difference in terms of correctness or usefulness in any application, but it makes the notation a little cleaner in some cases. The literature on separator theorems is big, and I'm certainly not familiar with it all, so likely this point has been made already several times in several papers. I'd be interested to find out which ones they are.

At one corner of the UCI campus, there's a bridge over San Diego Creek that I drive across maybe twice a week. There's also a bike path that follows the creek under the bridge. But while looking for some nearby graffiti this weekend I discovered another feature, visible neither from the road nor the bike path: someone has turned one of the concrete buttresses of the bridge into an impromptu climbing wall by cementing small stones onto it. It's a traverse rather than a climb, with a short drop onto soft dirt, so no ropes needed. I didn't think to bring climbing shoes, so I can't report how usable it is, but it seemed like a creative use for an otherwise bare wall.

I'm not convinced I captured much of interest, but I put a few photos online. The local swallows don't need handholds or footholds to climb, but the've also made their own attachments to the bridge, at the eave just under the edge of the bridge's deck; I included a shot of them, too.

I have a new preprint on arXiv: Ramified Rectilinear Polygons: Coordinatization by Dendrons (with Hans-Jürgen Bandelt and Victor Chepoi; arXiv:1005.1721).

This is a study of the graphs that can be embedded in a distance-preserving way into the Cartesian products of two trees, and the cell complexes that one gets by filling in the quadrilaterals of such a graph by rectangles. The title refers to the fact that any orthogonal polygon can be formed in this way, leading to a system of coordinates in which the usual Cartesian x and y axis lines are replaced by trees; geodesic Manhattan distance within the polygon is just the sum of the coordinatewise distances.

A graph that is an isometric subgraph of the product of two trees must be a cube-free median graph, but in some ways these graphs are simpler than the class of all cube-free median graphs: for instance, they can be recognized in linear time using LexBFS, whereas recognition of cube-free median graphs is provably equivalent to testing for the existence of triangles in sparse graphs, a problem that is not known to be solvable more quickly than O(n^1.41)

Why only two trees? Because the theory becomes very messy very quickly beyond that. In particular, k-coloring a graph is almost the same thing as embedding its simplex graph onto a product of k trees, so it's NP-complete to tell whether a graph is an isometric subgraph of three trees.

Here are a few photos from Sky Park, an industrial complex in Irvine near the airport, under the landing path of the planes. Although I didn't focus on them, it's the home of quite a few interesting small businesses, including the aikido dojo my son trains at.