Homeomorphism (graph theory)

<h2 id="subdivision-and-smoothing">Subdivision and smoothing</h2>
In general, a subdivision of a graph G (sometimes known as an expansion<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>) 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 preserve their propagating direction.
For example, the edge e, with endpoints {u,v }:
can be subdivided into two edges, e1 and e2, connecting to a new vertex w of <a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a>-2, or <a href="/facts/Directed_graph/YBdfQ0um">indegree</a>-1 and <a href="/facts/Directed_graph/YBdfQ0um">outdegree</a>-1 for the directed edge:
Determining whether for graphs G and H, H is homeomorphic to a subgraph of G, is an <a href="/facts/NP-complete/NFPv56DU">NP-complete</a> problem.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>

<h3>Reversion</h3>
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 <a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a>-2 (i.e., 2-valent) vertices can be smoothed. The limit of this operation is realized by the graph that has no more <a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a>-2 vertices.
For example, the simple <a href="/facts/Connectivity_(graph_theory)/FSNjsYhz">connected</a> graph with two edges, e1 {u,w } and e2 {w,v }: 
has a vertex (namely w) that can be smoothed away, resulting in:

<h3>Barycentric subdivisions</h3>
The <a href="/facts/Barycentric_subdivision/hsk1bw6b">barycentric subdivision</a> subdivides each edge of the graph. This is a special subdivision, as it always results in a <a href="/facts/Bipartite_graph/xWcXV9MB">bipartite graph</a>. This procedure can be repeated, so that the nth barycentric subdivision is the barycentric subdivision of the n−1st barycentric subdivision of the graph. The second such subdivision is always a <a href="/facts/Simple_graph/kw3eIBUe">simple graph</a>.

<h2 id="embedding-on-a-surface">Embedding on a surface</h2>
It is evident that subdividing a graph preserves <a href="/facts/Planar_graph/plREagr9">planarity</a>. <a href="/facts/Kuratowski%27s_theorem/Enph2grQ">Kuratowski's theorem</a> states that 

a <a href="/facts/Finite_graph/kw3eIBUe">finite graph</a> is planar <a href="/facts/If_and_only_if/bYSxGJ66">if and only if</a> it contains no <a href="/facts/Glossary_of_graph_theory/W0MqKkyE">subgraph</a> homeomorphic to K5 (<a href="/facts/Complete_graph/AYD6hUqI">complete graph</a> on five vertices) or K3,3 (<a href="/facts/Complete_bipartite_graph/C1RYIdpX">complete bipartite graph</a> on six vertices, three of which connect to each of the other three).
In fact, a graph homeomorphic to K5 or K3,3 is called a <a href="/facts/Kuratowski%27s_theorem/Enph2grQ">Kuratowski subgraph</a>.
A generalization, following from the <a href="/facts/Robertson%E2%80%93Seymour_theorem/J7g4CJ74">Robertson–Seymour theorem</a>, asserts that for each <a href="/facts/Integer/PUwwrawx">integer</a> g, there is a finite obstruction set of graphs 
 
 
 
 L
 (
 g
 )
 =
 
 {
 
 G
 
 i
 
 
 (
 g
 )
 
 
 }
 
 
 
 {\displaystyle L(g)=\left\{G_{i}^{(g)}\right\}}
 
 such that a graph H is <a href="/facts/Graph_embedding/IyBA3ttM">embeddable</a> on a surface of <a href="/facts/Genus_(mathematics)/o1Yhf8ty">genus</a> g if and only if H contains no homeomorphic copy of any of the 
 
 
 
 
 G
 
 i
 
 
 (
 g
 )
 
 
 
 
 
 {\displaystyle G_{i}^{(g)\!}}
 
. For example, 
 
 
 
 L
 (
 0
 )
 =
 
 {
 
 
 K
 
 5
 
 
 ,
 
 K
 
 3
 ,
 3
 
 
 
 }
 
 
 
 {\displaystyle L(0)=\left\{K_{5},K_{3,3}\right\}}
 
 consists of the Kuratowski subgraphs.

<h2 id="example">Example</h2>
In the following example, graph G and graph H are homeomorphic.

Graph GGraph 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.

<h3>mixed graph</h3>
The following <a href="/facts/Mixed_graph/6W2VCsLJ">mixed graphs</a> are homeomorphic. The directed edges are shown to have an intermediate arrow head.

Graph GGraph H
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Minor_(graph_theory)/qn5eI22T">Minor (graph theory)</a></li>
<li><a href="/facts/Edge_contraction/PRqKXEkj">Edge contraction</a></li></ul>

<h2 id="further-reading">Further reading</h2>
<ul><li>Yellen, Jay; Gross, Jonathan L. (2005), Graph Theory and Its Applications, Discrete Mathematics and Its Applications (2nd ed.), Chapman & Hall/CRC, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-1-58488-505-4</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn: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 
 
 
 
 G
 
 
 {\displaystyle G}
 
 and 
 
 
 
 H
 
 
 {\displaystyle H}
 
 are homeomorphic as graphs if and only if they are homeomorphic as topological spaces <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn: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. <a href="978-0-486-67870-2" target="_blank">978-0-486-67870-2</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn: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. <a href="/wiki/Hamiltonian_cycle" target="_blank">/wiki/Hamiltonian_cycle</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
</ol>

Homeomorphism (graph theory) open-in-new

Homeomorphism (graph theory)