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 (as they are usually depicted in diagrams), then two graphs are homeomorphic to each other in the graph-theoretic sense precisely if their diagrams are homeomorphic in the topological sense.
In general, a subdivision of a graph G (sometimes known as an expansion) is a graph resulting from the subdivision of edges in G. The subdivision of some edge e with endpoints {u, v} yields a graph containing one new vertex w, and with an edge set replacing e by two new edges, {u, w} and {w, v}. For directed edges, this operation shall preserve their propagating direction.
For example, the edge e, with endpoints {u, v}:
can be subdivided into two edges, e<sub>1</sub> and e<sub>2</sub>, connecting to a new vertex w of degree-2, or indegree-1 and outdegree-1 for the directed edge:
Determining whether for graphs G and H, H is homeomorphic to a subgraph of G, is an NP-complete problem.
The reverse operation, smoothing out or smoothing a vertex w with regards to the pair of edges (e<sub>1</sub>, e<sub>2</sub>) incident on w, removes both edges containing w and replaces (e<sub>1</sub>, e<sub>2</sub>) with a new edge that connects the other endpoints of the pair. Here, it is emphasized that only degree-2 (i.e., 2-valent) vertices can be smoothed. The limit of this operation is realized by the graph that has no more degree-2 vertices.
For example, the simple connected graph with two edges, e<sub>1</sub> {u, w} and e<sub>2</sub> {w, v}:
has a vertex (namely w) that can be smoothed away, resulting in:
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 n<sup>th</sup> barycentric subdivision is the barycentric subdivision of the nâÂÂ1st barycentric subdivision of the graph. The second such subdivision is always a simple graph.
It is evident that subdividing a graph preserves planarity. Kuratowski's theorem states that
In fact, a graph homeomorphic to K<sub>5</sub> or K<sub>3,3</sub> 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.
In the following example, graph G and graph H are homeomorphic.
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:
Therefore, there exists an isomorphism between <nowiki>G'</nowiki> and <nowiki>H'</nowiki>, meaning G and H are homeomorphic.
The following mixed graphs are homeomorphic. The directed edges are shown to have an intermediate arrow head.