Homeomorphism (graph Theory) - Subdivisions

Subdivisions

In general, a subdivision of a graph G (sometimes known as an expansion)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}:

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

The reverse operation, smoothing out or smoothing a vertex w with regards to the pair of edges (e,f) incident on w, removes both edges containing w and replaces (e,f) with a new edge that connects the other endpoints of the pair. Here it is emphasized that only 2-valent vertices can be smoothed.

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

Determining whether for graphs G and H, H is homeomorphic to a subgraph of G, is an NP-complete problem.