Diagrams

03Jun12

The diagram above is from a paper of mine which, as I found out today, was published last year! It is in ACM Transactions on Algorithms, although their website still lists the “current issue” as 2010 and they didn’t tell me when it went to press. The paper, joint with Ramki Thurimella, is about using a simple idea from graph theory to obtain dramatic speedups for distributed algorithms. An Eulerian subgraph is one with even degree at every node. The cycle space is the family of all Eulerian subgraphs; it is a vector space because when you add two Eulerian subgraphs mod 2, the result is another Eulerian subgraph. We show that you can efficiently sample a random Eulerian subgraph and use the samples to quickly determine if the graph is 3-edge-connected, or 2-vertex-connected. The picture above, which is a bunch of pure graph theory, is used in the implementation for the parallel model of computing.

Here is a second picture:

This one is from ongoing work with several collaborators from the Egerváry Research Group in Budapest. It shows a g-polymatroid on the left; if we relax the blue constraint we get the polyhedron on the right which is not a g-polymatroid. This picture was much harder for me to put together! I had drawn these polyhedra originally using Maple and/or Sage, which are great for doing anything polyhedral (even in more than 3 dimensions). But exporting to a .pdf-friendly format was next to impossible! What I have finally settled on is the pst-solides3d package for LaTeX, which is pretty professional and gives you very good control over the appearance.

I also considered using Asmpytote with the media9 package, which lets you actually rotate the 3d diagrams while you are reading the paper! Here is a demo file where you can try it out; it doesn’t work for my in-browser pdf previewer, but is fine when opened as a stand-alone pdf. It seems somewhat less author-friendly and more likely to crash your .pdf reader. But, it’s reasonable to say that the best way to learn about 3D geometry should be to play with the object as if it were in your own hands.

Advertisements


No Responses Yet to “Diagrams”

  1. Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: