Paper citation graph for GD

Here are a few pictures from the citation network of the Graph Drawing conference (GD). The nodes represent the papers that were published in GD. There are 821 papers in the data set. A edge is pointing from node a to node b, if the paper associated to node a cites the paper associated to node b. Of course this only encodes the citations within the GD conference. In particular, it ignores the fact that many papers were published subsequently as journal versions. However it is nice to expore this data. There are about 40% isolated nodes, and 20% of the nodes have only degree 1. The network has one big connected component and several very small components. I have generated a few pictures of the big component, listing only papers that have at least one GD citation. The size of the nodes reflect the in-degree (citations) of a paper.

Continue reading

Graph Drawing 2013 in Bordeaux

Last week I attended the Graph Drawing conference in the wonderful city of Bordeaux, France. The conference was smoothly organized, they had sensational food and we had 30°C sunny weather. All lunches and the conference dinner were organized as buffets without seating. I enjoyed this very much, since I was able to meet much more people than in the usual setting. So thanks a lot for the organizers for hosting a great conference.

Continue reading

A Small Grid Embedding of the Dodecahedron

One of the main area of research are grid embeddings of convex 3d polytopes. By Steinitz' theorem every 3-connected planar graph can be embedded as a convex 3d polytope, even with integer coordinates. The question is, how large have the coordinates to be, in terms of the number of the vertices . Although there were a series of improvements over the grid size of Steinitz' construction (of course he was not interested in getting integer or even small coordinates) the current best algorithm uses coordinates of size . At least for triangulations (simplicial polytopes) I expect however that the necessary grid size is bounded by a polynomial. In fact, the current lower bound is only .

This post is about embedding a very special graph as a convex 3d polytope: the graph of the dodecahedron. In other words, what is the smallest grid in which one can embed a (nonregular) dodecahedron. The dodecahedron is interesting since it is the smallest example with no triangular and quadrilateral faces. This seems to be a more tricky case, at least for the current best algorithm that would embed the dodecahedron on the grid with z-coordinates ranging between zero and 11 083 163 098 782 678 334 820 352. Of course we can do better. Francisco Santos found an embedding that fits inside the 8 x 6 x 4 grid. Also, there is a very symmetric realization known as pyritohedron that needs a 12 x 12 x 12 grid.

Continue reading

Graph Drawing 2013 - Accepted Papers

I just saw that the accepted papers of this years Symposium of Graph Drawing have been posted (see here for titles and authors). I have one paper about grid embeddings of 3d polytopes via a realization of a dual polytope which is joint work with my student Alex.

I am looking forward to go to Bordeaux in September and will post my impressions.

Bending Reality Website

In a former post I wrote about the art exhibition "Bending Reality" that took place at Schloss Dagstuhl. The exhibition was part of a workshop about curved graph drawings. I am happy to announce that the organizers have set up a webpage that contains all the exhibits (including the nice metro maps of Maxwell Roberts). One of my favorites is the "Flowerpot" by Günter Rote.

Accepted Papers for WG 2013

The 39th International Workshop on Graph-Theoretic Concepts in Computer Science, WG for short, takes this year place in Lübeck, Germany. Today I found out that their webpage lists the accepted papers (titles and authors but no abstracts).

Fortunately, I also have a paper at this year's WG. The paper is about drawing graphs with circular arcs. Since I never been to WG before I am looking forward to go to a new conference. The list of accepted paper looks actually very interesting - there are quite a few talks about graph drawing and about representation of graphs.