Homeomorphism (graph theory)

In graph theory, two graphs $G$ and $G\text{'}$ are homeomorphic if there is an isomorphism from some subdivision of $G$ to some subdivision of $G\text{'}$. 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.

ubdivisions

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 {"u","v"} yields a graph containing one new vertex "w", and with an edge set replacing "e" by two new edges with endpoints {"u","w"} and {"w","v"}.

For example, the edge "e", with endpoints {"u","v"}:has a vertex (namely "w") 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 "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 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 subgraph homeomorphic to "K"₅ (complete graph on five vertices) or "K"_3,3 (complete bipartite graph on six vertices, three of which connect to each of the other three).

In fact, a graph homeomorphic to "K"₅ or "K"_3,3 is called a Kuratowski subgraph.

A generalization, flowing from the Robertson–Seymour theorem, asserts that for each integer "g", there is a finite obstruction set of graphs $L(g)\; =\; \{G\_\{i\}^\{(g)\}\}$ 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)\; =\; \{K\_\{5\},\; K\_\{3,3\}\}$ contains 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.

ee also

*Minor (graph theory)
*Edge contraction

References

*