As a follow-up to the problem of coloring triangle-free line segment intersection graphs that I posted the other day, here's another line segment intersection representation of the Grötzsch graph. This time I drew it with only four different slopes of line segments, making it obvious that it can be 4-colored (just use a different color for each slope). And conversely the fact that this graph requires four colors implies that I couldn't have drawn it with fewer than four slopes. Is there a bound on the number of distinct slopes needed to realize all triangle-free line segment intersection graphs? It seems likely to be hard to prove that this number is bounded, if it is, since that would also solve the coloring problem. But maybe it's easy to come up with a family of triangle-free line segment intersection graphs that require an unbounded number of slopes?



A natural candidate for an (infinite) line segment intersection graph requiring an unbounded number of slopes is the order-4 pentagonal tiling of the hyperbolic plane, the Klein model of which forms a triangle-free line segment arrangement in the Euclidean plane. But I don't see an easy way to get a handle on how many slopes it needs.

Aesthetics of commutative diagrams. An interesting discussion of graph drawing in the context of graphs that represent mathematical formulas. Does one lay them out in a nice grid pattern which makes the formulas easier to read, or does one choose a less uniform vertex placement in which the global shape of the diagram (its outside face) conveys the intended meaning of the diagram?

The graph drawn above is the planar dual to the Herschel graph. The Herschel graph has nine quadrilateral faces, so its dual is a 9-vertex 4-regular planar graph, and therefore can be drawn as the arrangement graph of a system of smooth curves, or as in this case as the self-crossings of a single smooth curve.

Much of the research in graph drawing uses a drawing style in which edges are drawn as straight line segments, or as sequences of straight line segments articulated by "bends", corners where two line segments meet. But I think that, in many cases, smooth curves can create a more interesting aesthetic effect, that the extra freedom inherent in drawing curves makes it possible to spread out the features of the drawing more evenly, and that smooth curves are likely to be easier for the eye to follow than sharp bends.

No doubt Mark Lombardi would agree.

I just finished uploading five new sets of photos:

• Mathematical sculpture at Trinity College Dublin. Or sort-of mathematical: the artist may have intended one of these sculptures to model DNA, but to a topologist it looks like a torus link. Apparently every year the Hamilton Workshop on Geometry and Topology uses one of these as a logo, but they're running out: soon they'll have to go with the kitschy sculpture of a buxom Molly Malone outside the college gate.


• Dublin. Or the parts of it that I saw outside of Trinity and Guinness. With my usual complement of graffiti.


• The Guinness Storehouse. Supposedly Ireland's biggest tourist attraction. I didn't take many photos inside, although I found the tour quite interesting; most of the photos are of the 360-degree view of the Guinness brewery that one gets from the bar at the top of the tour.


• Chicago. The weather was not really conducive to photography but I took a couple of shots anyway.


• Graph Drawing 2009. If you didn't go, now's your chance to see what you missed. If you did go, you can see how many photos you and your friends are in. I hope none of the ones I kept are too embarrassing or unflattering. ETA: The GD09 web site now also links to another set of photos by Pranava Jha.

After two conferences I'm too tired to successfully post anything serious. So, since Graph Drawing lacks a public business meeting at which to present these, here instead are some statistics on acceptances and rejections at the conference.

( Read more... )

Two of the papers presented today at Graph Drawing (and one earlier at WADS) concerned drawings in which edges that cross are required to do so at a high angle. One of today's papers ("On the perspectives opened by right angle crossing drawings", by Angelini et al) included some results on bounded degree graphs, showing that graphs with sufficiently low degree bounds could be given drawings with right-angled crossings and few bends per edge. The other paper ("Area, curve complexity, and crossing resolution of non-planar graph drawings", by Di Giacomo et al) generalized the problem, looking not just at right angled drawings but at drawings in which all crossings have an angle bounded away from zero; the "crossing resolution" of the title is the minimum angle of any crossing. So what if we put both of these together and look at the crossing resolution of bounded-degree graphs?

( Read more... )

ETA: János Pach points out that the same relation between geometric thickness and crossing resolution allows one to prove an O(1/n) bound on the crossing resolution of n-vertex complete graphs from known results on geometric thickness of complete graphs, improving a logarithmic bound from the Di Giacomo et al paper and an O(1/√n) bound obtained from a result of Aronov et al. that any n points in general position have Ω(√n) pairwise crossing line segments.

Two papers of mine on the arxiv, one a few weeks old and one newly appearing:

Optimal angular resolution for face-symmetric drawings (with Kevin Wortman). In this paper, we consider drawings of planar partial cubes in which all interior faces are centrally symmetric convex polygons, as in my previous paper Algorithms for Drawing Media from Graph Drawing 2004. Among all drawings of this type, we show how to find the one with optimal angular resolution. The specific motivation was to improve the drawing I showed in this post to be more legible, so that it could be used in my recent paper on squaregraphs with Bandelt and Chepoi. The solution involves the parametric negative cycle detection problem: given a graph in which the edge weights are linear functions of a parameter λ, find the minimum value of λ for which the graph contains no negative cycles. However, unlike my work with Kevin on metric embedding, the parametric graph coming from this problem falls into a special case solved by known algorithms, so we didn't need to invent a new cycle detection algorithm. We're preparing a version of this for journal publication, but the current version doesn't yet have all of the referee's requested revisions incorporated, because I wanted to have a version of this available in order to cite it from the next one:

Graph-theoretic solutions to computational geometry problems. A survey on situations in which geometric problems that are stated without reference to any graph can be solved efficiently by defining some auxiliary graph from the input and performing some graph-theoretic algorithm. For instance, the problem of partitioning a polygon with axis-parallel sides into as few rectangles as possible may be solved in polynomial time by constructing the bipartite intersection graph of its axis-aligned diagonals and finding a maximum matching in this graph. Essentially, this is a paper version of my talk from WG, and I wrote it backwards from the way I usually write papers and talks: usually I write a paper, then later (after it is accepted to a conference) write slides based on that paper, and deliver a talk based on those slides. But this time, I had no paper written when I needed the slides and a talk, so I worked out how to organize the material as part of the process of making slides and giving the talk, and reused the same organization for the paper itself. I used to write survey papers regularly, but lately I've tended to focus that energy on my Wikipedia editing, so it was refreshing to write something like this and not feel constrained to avoid including original research (such as the claim that kinggraphs are 4-chromatic) or original syntheses of existing ideas (the overall point of the survey).

In the revisions of one of my papers, I needed an illustration of the graph shown below, which comes from an NP-completeness reduction. This is a confluent drawing: two vertices are connected by an edge whenever there is a smooth path between them. (The paths are allowed to self-intersect, so for instance all 30 outer vertices form a clique.)



I think it's a great illustration of the power of confluent graph drawing: the graph has 37 vertices, 536 edges, and an average degree of nearly 29, but despite being so dense the graph has a lot of structure and the drawing makes the structure apparent.

There are various standard mistakes that we eventually learn not to do when choosing titles for papers: putting a mathematical formula into a title, for instance, makes it much more difficult for citation databases such as Google Scholar to handle it correctly.

Here's another one: making your title be an accurate technical description of the techniques you use without any hint of what you're using them for. Tonight's example: A Fast Multigrid Algorithm for Energy Minimization Under Planar Density Constraints, by Ron, Safro, and Brandt. What you wouldn't be able to guess from the title alone: this is really a graph drawing paper.

What it's actually about, as far as I can tell from a quick read, is a fairly standard graph drawing type problem: taking as input a drawing of a graph and improving it by treating the edges as springs and moving the vertices around to minimize spring energy. The new variation seems to be to perform this optimization under a set of constraints that force the vertices to remain spread out uniformly in the drawing area, rather than relying on a repulsive force to keep them apart and having to balance the repulsions and attractions. And with this explained, the title makes sense: “energy minimization” refers to the spring energy of the graph edges and “planar density constraints” refers to the way the vertices are kept apart from each other. But there's nothing in the title that might tempt a graph drawer to get this far.

The call for papers for Graph Drawing 2009 is now up. The important details are that the submission deadline is May 31, the conference is September 22–25, and the location is Chicago.

As the call for papers describes, we're interested not only in papers about software and algorithms for visualizing “web maps, software engineering diagrams, database schemas, chemical structures and molecules” (arguably the main topic of the conference) but also about closely related topics including algorithms for geometric computing involving graphs, the mathematics of graph embeddings, user interfaces and usability studies for graph drawing systems, and applications of graph drawing in other areas.

So, if you haven't done so already, start thinking about what you'd like to submit!

Complexity doesn't have to be ugly: Glyphobet links to dburrows' diagrams of the apt system as an example of why automated graph drawing tools could benefit with interaction from skilled graphic designers.

Beyond Glyphobet's point (which I agree with) I think the drawings could also benefit from some of my own research, on confluent drawing. It's not that the drawing is nonplanar — one benefit of confluence is replacing many crossing single-to-single connections by a single many-to-many connection, reducing the number of crossings, but that isn't an issue in this drawing. Rather, what I think would most improve the drawings (beyond a little more care in vertex placement and edge routing so that unnecessary crossings and close pairs of edges are avoided) would be to replace groups of single-to-single connections, all with the same source or sink and all with the same label, by a single-to-many or many-to-single confluent connection with only one label. The label clutter is as big or bigger an issue in these drawings than the edge clutter, and confluence can help with that.

In the comments to a recent posting, the question “how do I make my drawings” came up again, so I thought I would put together a tutorial describing how I made one of my drawings, a new illustration for a Wikipedia article on crown graphs (complete bipartite graphs minus a matching, which I also discussed in this earlier post in the context of covering these graphs by bicliques).

( Read more... )

I'm now in New York for ALENEX (today) and SODA (the following three days). The most interesting juxtaposition at ALENEX, for me, was the pair of back-to-back talks by Martin Nöllenburg and Siamak Tazari.

( Tanglegram drawings and planar graph Steiner trees )

I've previously posted about drawing this graph, the unique 3-regular 24-vertex symmetric graph, here, here, and here.

Today a co-author pointed me towards tikz, a package for drawing things in TeX. And what do I find as the most recently posted example? The same graph, drawn in yet another way. They call it the "star graph", but (1) that's the name for the infinite family of Cayley graphs of S_n to which it belongs, and (2) it's a bad name because a star is also a tree with one non-leaf node; the Cayley graphs have as generators a set of swaps forming a star tree. Anyway, their drawing is pretty close to my drawing of it as a hexagonal torus tiled with smaller hexagons, but with the wraparound torus edges drawn across the planar part. For comparison, here are the tikz image (hotlinked) and my image:

( Read more... )

It seems to be the standard position in graph drawing research that edge crossings are bad, and that minimizing crossings is a good way to make a drawing better. So I was interested to see a new preprint, “An Eye Tracking Study into the Effects of Graph Layout,” by Weidong Huang, which argues that crossings themselves are not so harmful, but rather that it is the crossings with sharp crossing angle that most confuse readers of the drawings. Huang bases these conclusions on actual experiments with actual humans, something I think there hasn't been enough of in the graph drawing community.

This should mean, for instance, that the two-layer drawings produced by my paper with Duncan and Kobourov on geometric thickness of low degree graphs should generally be quite legible, as the edges in one layer are generally horizontal while the edges in the other layer are generally vertical, producing nearly right angled crossings. For instance, here's a drawing of this type of the Nauru graph; I've been using this drawing as a bad example in some of my talks (because it doesn't indicate the graph's high degree of symmetry) but in terms of legibility of individual vertices and edges I think it's pretty good, even at this small size.



In this drawing the angular resolution at the vertices is much worse than at the crossings, so maybe that's a tradeoff to be explored. Probably there are some interesting additional algorithmic problems to be solved involving finding drawings with good angular resolution at the crossings.

The Graph Drawing 2008 web site now has hundreds of photos from the conference. Probably not of interest unless you were a participant. And the following more specific links are probably not of interest unless you're me, but I found a few of myself at the opening night reception with Maarten Löffler, at a coffee break with Bettina Speckmann, watching the talks with Elena Mumford, giving my talks on xyz graphs and diamond lattices, chatting with Roberto Tamassia, outside the talk site with Alex Wolff, and at the banquet.

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.

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!

You remember that genus-four surface embedding of the Nauru graph (the unique 3-regular 24-vertex symmetric graph) that I couldn't figure out how to model in SketchUp? This weekend I tried modeling it again. This time I wrote a Python program to output a POVray program to generate the model. Here it is:



The flat surface texture, the dark outline of the graph edges, and the rough points where the edges bend around sharp corners and don't quite meet correctly at the corners all add up to a vaguely cartoony appearance, despite this being a high-quality antialiased raytrace, but I kind of like it that way.

On a vaguely-related note, I found my long-lost discrepancy-for-supersampling-for-antialiasing coauthor Don Mitchell's new web page. Don worked for Microsoft until around 1999, when I lost track of him. Nowadays he runs two smaller graphics companies in the Seattle area.

Two papers my coauthors and I recently uploaded to the arXiv:

( Succinct Greedy Graph Drawing in the Hyperbolic Plane )

( Self-Overlapping Curves Revisited )