Halin's grid theorem
id:
halin-s-grid-theorem-263-4330673
title:
Halin's grid theorem
text:
In graph theory, a branch of mathematics, Halin's grid theorem states that the infinite graphs with thick ends are exactly the graphs containing subdivisions of the hexagonal tiling of the plane. It was published by Rudolf Halin (1965), and is a precursor to the work of Robertson and Seymour linking treewidth to large grid minors, which became an important component of the algorithmic theory of bidimensionality.
brand slug:
wiki
category slug:
encyclopedia
description:
Theorem about infinite graphs
original url:
https://en.wikipedia.org/wiki/Halin%27s_grid_theorem
date created:
date modified:
2021-10-29T02:41:42Z
main entity:
{"identifier":"Q5642351","url":"https://www.wikidata.org/entity/Q5642351"}
image:
fields total:
13
integrity:
14