• So far, the applets illustrate only the basic pebble game for k edge-disjoint spanning trees. In this case, l=k, to match the terminology of (the current version of) our paper.
  We have several generalizations which will be posted soon, including the cases going beyond spanning trees and the Component Pebble Game, which computes maximal sparse subgraphs (components).
• The input graph appears on the left canvas. The right canvas depicts the (basic) pebble game state step by step.
• Edges are inserted in an arbitrary order (the insertion order may change next time you play it).
• The acceptance condition is: at least l+1 pebbles on the two endpoints of the inserted edge. The implementation that you see here enforces an even stronger rule. Hopefully this makes it easier to follow what's going on, here and in the proof of the component algorithm, and gives you a chance to see the path reversal at work during the pebble-collecting phase.
  • The orientation of the edge is chosen beforehand. The green vertex will be the source, the red will be the destination of the edge.
  • k pebbles are gathered on the red vertex and at least 1 pebble must be present on the green vertex.
• The Graphs menu allows you to choose from a small set of wired-in examples.
• Small bug(s): sometimes when you click Step forward for the first time, more than k pebbles may show on one vertex. This is just the viewer behaviour, internally everything is fine - we'll fix it soon. Also, sometimes a pair of parallel edges oriented in opposite directions may appear as a single double-oriented edge: this comes the Java library used in the implementation, so let's accept it for the time being :-)

3-tree pebble games.

Body-and-bar structures and 6-tree pebble games.