Interactive element. An interactive graph elimination sandbox. Click nodes to eliminate them. Use the botton in the top right to generate a new random graph.
Graph Elimination
Graph Elimination
This element demonstrates the importance of ordering for the sparsity of a triangular transport map. Starting from a true graph (left), click on any black node to eliminate it. Eliminating a node has the following effects:
It fills the lower-most available row in the map structure subplot (bottom right).
It forms a clique among the node's neighbours. This can create new fill-in edges (red).
The goal is to generate a map structure with as few edges as possible. Try to find an elimination ordering that minimizes the fill-in. Remember that sometimes fill-in is unavoidable.