Homeomorphism (graph theory)

In graph theory, two graphs G {displaystyle G} and G ′ {displaystyle G'} are homeomorphic if there is a graph isomorphism from some subdivision of G {displaystyle G} to some subdivision of G ′ {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 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. In graph theory, two graphs G {displaystyle G} and G ′ {displaystyle G'} are homeomorphic if there is a graph isomorphism from some subdivision of G {displaystyle G} to some subdivision of G ′ {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 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. 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, e1 and e2, connecting to a new vertex w: The reverse operation, smoothing out or smoothing a vertex w with regards to the pair of edges (e1 ,e2 ) incident on w, removes both edges containing w and replaces (e1 ,e2 ) 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, e1 {u,w} and e2 {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. 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 nth barycentric subdivision is the barycentric subdivision of the n-1th barycentric subdivision of the graph. The second such subdivision is always a simple graph.