Mikołaj Bojańczyk

Tree width à la metro


August 11, 2015

Here is a way of drawing graphs of bounded tree width, inspired by metro maps. The horizontal black lines are graph edges, the coloured shapes are vertices, and the gray background is the tree underlying the decomposition.

tree-width-metro

 

The mathematical content of the picture is that a graph has tree width k if and only if it is a subgraph of a (k+1)-colourable chordal graph (thanks to Michał Pilipczuk for pointing this out).

 

Leave a Reply

Your email address will not be published. Required fields are marked *