Homeomorphism (graph theory)

From Wikipedia, the free encyclopedia

In graph theory, two graphs G and G′ are homeomorphic if there is an 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 Subdivisions
- 1.1 Barycentric Subdivisions
2 Embedding on a surface
3 See also
4 Reference

[edit] Subdivisions

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

For example, the edge e, with endpoints {u,v}:

(u)--e--(v)

can be subdivded into two edges, e₁ and e₂, connecting to a new vertex w:

(u)--e₁--(w)--e₂--(v)

The reverse operation, smoothing out a vertex w with regards to the pair of edges (e,f) incident on w, removes all edges containing w and replaces (e,f) with a new edge that connects the other endpoints of the pair.

For example, the simple connected graph with two edges, e₁ {u,w} and e₂ {w,v}:

(u)--e₁--(w)--e₂--(v)

has a vertex (namely w) that can be smoothed away, resulting in::

(u)--e--(v)

The problem of determining whether two graphs G and G′ have subgraphs H, H′ that are homeomorphic is an NP-complete problem.

[edit] 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.

[edit] 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 imbeddible 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.