Dynamic Citation Graph

Almost a year ago I had a post about citation networks of interconnected communities. Simply speaking, I displayed a citation network (which paper cites which) of two related conferences. As conferences pairs I picked GD/WG, ICALP/ESA, and SWAT/WADS. All these conferences had their proceedings published by Springer, which made it easier to get the data via crawling through the springerlink portal.

Although the pictures were really nice (rendered in gephi) I wanted to have a more dynamic visualization. This weekend I finally found the time to prepare something. I picked the biggest component (82 nodes) in the SWAT/WADS network, since it was the smallest interesting (sub)graph I found. My goal was to let the user filter the data by year and get a dynamically increasing citation graph over time.

Continue reading

Citation graphs of interconnected communities

As a follow-up to my previous post about the citation graph of the Graph Drawing conference I computed a few more drawings with gephi. This time I have concentrated on visualizing connections between conferences with a similar scope. I improved my "springerlink-crawler". In the current version I first scan all the titles and then I scan for references where the matching is done by title. By this I will also detect references to journal versions if they have the same title. Again the citation graphs are very sparse, since they only reflect citations within the conferences. The data set is very likely not 100% accurate, but my impression is that it is good enough to illustrate a few interesting things.

Continue reading

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

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 n. 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 2^{O(n)}. 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 \Omega(n^{3/2}).

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

Vertex-first projections of hypercubes

A few days ago I was answering a question posted on math.stackexchange.com. It was asked what would be the next polytope in the following sequence "Hexagon,Rhombic Dodecahedron,???"?

One possible answer for this question goes along the following lines: Both the hexagon and the rhombic dodecahedron are vertex-first projections of cubes. The hexagon is the projection of the 3-cube, and the rhombic dodecahedron is the projection of the 4-cube. So the next polytope in this sequence would be the vertex-first projection of the 5d cube. (I consider the vertex-first projection that aligns two opposing cube vertices along the normal vector of the projection hyperplane.)

Continue reading