{"id":499,"date":"2015-08-11T15:23:20","date_gmt":"2015-08-11T13:23:20","guid":{"rendered":"http:\/\/duch.mimuw.edu.pl\/~bojan\/?p=499"},"modified":"2015-08-19T17:32:16","modified_gmt":"2015-08-19T15:32:16","slug":"tree-width-a-la-metro","status":"publish","type":"post","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/posts\/tree-width-a-la-metro","title":{"rendered":"Tree width \u00e0 la metro"},"content":{"rendered":"<p>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.<\/p>\n<p><a href=\"http:\/\/www.mimuw.edu.pl\/~bojan\/upload\/tree-width-metro.svg\"><img decoding=\"async\" class=\"alignnone size-medium wp-image-510\" src=\"http:\/\/www.mimuw.edu.pl\/~bojan\/upload\/tree-width-metro.svg\" alt=\"tree-width-metro\" \/><\/a><\/p>\n<p>&nbsp;<\/p>\n<p>The mathematical content of the picture is that a graph has tree width <em>k<\/em> if and only if it is a subgraph of a (<em>k+1<\/em>)-colourable <a href=\"https:\/\/en.wikipedia.org\/wiki\/Chordal_graph\">chordal graph<\/a> (thanks to Micha\u0142 Pilipczuk for pointing this out).<\/p>\n","protected":false},"excerpt":{"rendered":"<p>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. &nbsp; The mathematical content of the picture is that a graph has tree width k if and only [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-499","post","type-post","status-publish","format-standard","hentry","category-posts"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/posts\/499"}],"collection":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/comments?post=499"}],"version-history":[{"count":2,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/posts\/499\/revisions"}],"predecessor-version":[{"id":514,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/posts\/499\/revisions\/514"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=499"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/categories?post=499"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/tags?post=499"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}