Graph homeomorphism

An equivalence relation on the set of graphs, characterizing their geometric properties. The notion of a graph homeomorphism is defined as follows. Subdivision of an edge $(a,b)$ of a graph $G$ is an operation involving the addition of a new vertex $v$, the removal of $(a,b)$, and the addition of two new edges $(a,v)$ and $(v,b)$. Geometrically, this operation consists in addition of some (interior) point $v$ on the line $(a,b)$; this point then becomes a new vertex. A graph $G'$ is called a subdivision of a graph $G$ if it can be obtained from $G$ by repeating the operation of edge subdivision several times. Two graphs $G_1$ and $G_2$ are said to be homeomorphic if they have isomorphic subdivisions (cf. Graph isomorphism).