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. Mind that fill-in is sometimes unavoidable.

Remark: Perfect elimination orderings only exist for chordal graphs. Graphs which feature (non-reducible) cycles of four or more nodes are non-chordal and have inevitable fill-in.