In graph theory, two graphs $G$ and $G'$ are **homeomorphic** if there is a graph isomorphism from some **subdivision** of $G$ to some **subdivision** of $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*_{5} 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 $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 $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 $G_{i}^{(g)}$. For example, $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.