Homeomorphism (graph theory)


In graph theory, two graphs and are homeomorphic if there is a graph isomorphism from some [|subdivision] of to some subdivision of. If the edges of a graph are thought of as lines drawn from one vertex to another, then two graphs are homeomorphic to each other in the graph-theoretic sense precisely if they are homeomorphic in the sense in which the term is used in topology.

Subdivision and smoothing

In general, a subdivision of a graph G is a graph resulting from the subdivision of edges in G. The subdivision of some edge e with endpoints yields a graph containing one new vertex w, and with an edge set replacing e by two new edges, and.
For example, the edge e, with endpoints :
can be subdivided into two edges, e1 and e2, connecting to a new vertex w:
The reverse operation, smoothing out or smoothing a vertex w with regards to the pair of edges incident on w, removes both edges containing w and replaces with a new edge that connects the other endpoints of the pair. Here it is emphasized that only 2-valent vertices can be smoothed.
For example, the simple connected graph with two edges, e1 and e2 :
has a vertex that can be smoothed away, resulting in:
Determining whether for graphs G and H, H is homeomorphic to a subgraph of G, is an NP-complete problem.

Barycentric Subdivisions

The barycentric subdivision subdivides each edge of the graph. This is a special subdivision, as it always results in a bipartite graph. This procedure can be repeated, so that the nth barycentric subdivision is the barycentric subdivision of the n-1th barycentric subdivision of the graph. The second such subdivision is always a simple graph.

Embedding on a surface

It is evident that subdividing a graph preserves planarity. Kuratowski's theorem states that
In fact, a graph homeomorphic to K5 or K3,3 is called a Kuratowski subgraph.
A generalization, following from the Robertson–Seymour theorem, asserts that for each integer g, there is a finite obstruction set of graphs such that a graph H is embeddable on a surface of genus g if and only if H contains no homeomorphic copy of any of the. For example, consists of the Kuratowski subgraphs.

Example

In the following example, graph G and graph H are homeomorphic.
G
H
If G' is the graph created by subdivision of the outer edges of G and H' is the graph created by subdivision of the inner edge of H, then G' and H' have a similar graph drawing:
G', H'
Therefore, there exists an isomorphism between G' and H', meaning G and H are homeomorphic.