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

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:

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.