Homeomorphism (graph theory)

Not to be confused with graph homomorphism.

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 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

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₁ and e₂, 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

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

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

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−1st 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, 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.

Example

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

Graph G

Graph 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:

Graph G′, H′

Therefore, there exists an isomorphism between G' and H', meaning G and H are homeomorphic.

mixed graph

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

Graph G

Graph H

See also

• Minor (graph theory)
• Edge contraction

References

1. 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 ${\displaystyle G}$ and ${\displaystyle H}$ are homeomorphic as graphs if and only if they are homeomorphic as topological spaces
2. 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.
3. 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

• 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