# Homeomorphism (graph theory)

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.^{[1]}

## Subdivision and smoothing

[edit]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 directed edges, this operation shall reserve their propagating direction.

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

can be subdivided into two edges, *e*_{1} and *e*_{2}, 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.^{[3]}

### Reversion

[edit]The reverse operation, **smoothing out** or **smoothing** a vertex *w* with regards to the pair of edges (*e*_{1}, *e*_{2}) incident on *w*, removes both edges containing *w* and replaces (*e*_{1}, *e*_{2}) 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*_{1} {*u*,*w* } and *e*_{2} {*w*,*v* }:

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

### Barycentric subdivisions

[edit]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*−1st barycentric subdivision of the graph. The second such subdivision is always a simple graph.

## Embedding on a surface

[edit]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*_{5}(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*_{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 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.

## Example

[edit]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 *G'* and *H'*, meaning *G* and *H* are homeomorphic.

### mixed graph

[edit]The following mixed graphs are homeomorphic. The directed edges are shown to have an intermediate arrow head.

## See also

[edit]## References

[edit]**^**Archdeacon, Dan (1996), "Topological graph theory: a survey",*Surveys in graph theory (San Francisco, CA, 1995)*, Congressus Numerantium, vol. 115, pp. 5–54, CiteSeerX 10.1.1.28.1728, MR 1411236,The name arises because and are homeomorphic as graphs if and only if they are homeomorphic as topological spaces

**^**Trudeau, Richard J. (1993).*Introduction to Graph Theory*. Dover. p. 76. ISBN 978-0-486-67870-2. Retrieved 8 August 2012.**Definition 20.**If some new vertices of degree 2 are added to some of the edges of a graph*G*, the resulting graph*H*is called an*expansion*of*G*.**^**The more commonly studied problem in the literature, under the name of the subgraph homeomorphism problem, is whether a subdivision of*H*is isomorphic to a subgraph of*G*. The case when*H*is an*n*-vertex cycle is equivalent to the Hamiltonian cycle problem, and is therefore NP-complete. However, this formulation is only equivalent to the question of whether*H*is homeomorphic to a subgraph of*G*when*H*has no degree-two vertices, because it does not allow smoothing in*H*. The stated problem can be shown to be NP-complete by a small modification of the Hamiltonian cycle reduction: add one vertex to each of*H*and*G*, adjacent to all the other vertices. Thus, the one-vertex augmentation of a graph*G*contains a subgraph homeomorphic to an (*n*+ 1)-vertex wheel graph, if and only if*G*is Hamiltonian. For the hardness of the subgraph homeomorphism problem, see e.g. LaPaugh, Andrea S.; Rivest, Ronald L. (1980), "The subgraph homeomorphism problem",*Journal of Computer and System Sciences*,**20**(2): 133–149, doi:10.1016/0022-0000(80)90057-4, hdl:1721.1/148927, MR 0574589.

## Further reading

[edit]- Yellen, Jay; Gross, Jonathan L. (2005),
*Graph Theory and Its Applications*, Discrete Mathematics and Its Applications (2nd ed.), Chapman & Hall/CRC, ISBN 978-1-58488-505-4