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 of a graph is an operation involving the addition of a new vertex , the removal of , and the addition of two new edges and . Geometrically, this operation consists in addition of some (interior) point on the line ; this point then becomes a new vertex. A graph is called a subdivision of a graph if it can be obtained from by repeating the operation of edge subdivision several times. Two graphs and are said to be homeomorphic if they have isomorphic subdivisions (cf. Graph isomorphism).