In graph theory, two graphs ${\displaystyle G}$ and ${\displaystyle G'}$ are homeomorphic if there is a graph isomorphism from some subdivision of ${\displaystyle G}$ to some subdivision of ${\displaystyle G'}$. If the edges of a graph are thought of as lines drawn from one vertex to another (as they are usually depicted in illustrations), 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.^[1]

Subdivision and smoothing

In general, a subdivision of a graph G (sometimes known as an expansion^[2]) 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 example, the edge e, with endpoints {u,v}:

Determining whether for graphs G and H, H is homeomorphic to a subgraph of G, is an NP-complete problem.^[3]

Barycentric subdivisions

The barycentric subdivision subdivides each edge of the graph. This is a special subdivision, as it always results in a bipartite graph

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^th barycentric subdivision is the barycentric subdivision of the n−1^th barycentric subdivision of the graph. The second such subdivision is always a simple graph.

Embedding on a surface

It

It is evident that subdividing a graph preserves planarity. Kuratowski's theorem states that

a finite graph is planar if and only if it contains no subgrap

In fact, a graph homeomorphic to K₅ or K_3,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 ${\displaystyle L(g)=\{G_{}^{}}$

A generalization, following from the Robertson–Seymour theorem, asserts that for each integer g, there is a finite obstruction set of graphs ${\displaystyle L(g)=\left\{G_{i}^{(g)}\right\}}$ 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 ${\displaystyle G_{i}^{(g)}}$. For example, ${\displaystyle L(0)=\left\{K_{5},K_{3,3}\right\}}$ consists of the Kuratowski subgraphs.

In the following example, graph G and graph H are homeomorphic.