Editing Homeomorphism (graph theory)

{{Short description|Concept in graph theory}}
{{Distinguish|graph homomorphism}}

In [[graph theory]], two [[graph (discrete mathematics)|graphs]] <math>G</math> and <math>G'</math> are '''homeomorphic''' if there is a [[graph isomorphism]] from some [[#Subdivision_and_smoothing|subdivision]] of <math>G</math> to some subdivision of <math>G'</math>.  If the edges of a graph are thought of as lines drawn from one [[vertex (graph theory)|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 [[homeomorphism|homeomorphic]] in the [[topology|topological]] sense.<ref>{{citation
 | last = Archdeacon | first = Dan
 | contribution = Topological graph theory: a survey
 | mr = 1411236
 | quote = The name arises because <math>G</math> and <math>H</math> are homeomorphic as graphs if and only if they are homeomorphic as topological spaces
 | pages = 5–54 |citeseerx=10.1.1.28.1728
 | series = Congressus Numerantium
 | title = Surveys in graph theory (San Francisco, CA, 1995)
 | volume = 115
 | year = 1996}}</ref>

==Subdivision and smoothing ==
In general, a '''subdivision''' of a graph ''G'' (sometimes known as an '''expansion'''<ref>{{cite book|last=Trudeau|first=Richard J.|title=Introduction to Graph Theory |year=1993 |publisher=Dover  |isbn=978-0-486-67870-2 |url=http://store.doverpublications.com/0486678709.html |access-date=8 August 2012 |pages=76 |quote='''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''.}}</ref>) 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''}:

[[Image:Graph subdivision step1.svg|150px|class=skin-invert]]

can be subdivided into two edges, ''e''<sub>1</sub> and ''e''<sub>2</sub>, connecting to a new vertex ''w'' of [[degree (graph theory)|degree]]-2, or [[Directed_graph#Indegree_and_outdegree|indegree]]-1 and [[Directed_graph#Indegree_and_outdegree|outdegree]]-1 for the directed edge:

[[Image:Graph subdivision step2.svg|150px|class=skin-invert]]

Determining whether for graphs ''G'' and ''H'', ''H'' is homeomorphic to a subgraph of ''G'', is an [[NP-complete]] problem.<ref>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''&nbsp;+&nbsp;1)-vertex [[wheel graph]], if and only if ''G'' is Hamiltonian. For the hardness of the subgraph homeomorphism problem, see e.g. {{citation
 | last1 = LaPaugh | first1 = Andrea S. | author1-link = Andrea LaPaugh
 | last2 = Rivest | first2 = Ronald L. | author2-link = Ron Rivest
 | doi = 10.1016/0022-0000(80)90057-4
 | issue = 2
 | journal = Journal of Computer and System Sciences
 | mr = 574589
 | pages = 133–149
 | title = The subgraph homeomorphism problem
 | volume = 20
 | year = 1980| doi-access = free
 | hdl = 1721.1/148927
 | hdl-access = free
 }}.</ref>

===Reversion===
The reverse operation, '''smoothing out''' or '''smoothing'''  a vertex ''w'' with regards to the pair of edges (''e''<sub>1</sub>, ''e''<sub>2</sub>) incident on ''w'', removes both edges containing ''w'' and replaces (''e''<sub>1</sub>, ''e''<sub>2</sub>) with a new edge that connects the other endpoints of the pair. Here, it is emphasized that only [[degree (graph theory)|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 (graph theory)|degree]]-2 vertices.

For example, the simple [[Connectivity (graph theory)|connected]] graph with two edges, ''e''<sub>1</sub> {''u'',''w''} and ''e''<sub>2</sub> {''w'',''v''}: 

[[Image:Graph subdivision step2.svg|150px|class=skin-invert]]

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

[[Image:Graph subdivision step1.svg|150px|class=skin-invert]]

===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''<sup>th</sup> 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 [[planar graph|planarity]].  [[Kuratowski's theorem]] states that 
: a [[finite graph]] is planar [[if and only if]] it contains no [[Glossary of graph theory#Subgraphs|subgraph]] '''homeomorphic''' to ''K''<sub>5</sub> ([[complete graph]] on five vertices) or ''K''<sub>3,3</sub> ([[complete bipartite graph]] on six vertices, three of which connect to each of the other three).

In fact, a graph homeomorphic to ''K''<sub>5</sub> or ''K''<sub>3,3</sub> is called a [[Kuratowski's theorem|Kuratowski subgraph]].

A generalization, following from the [[Robertson–Seymour theorem]], asserts that for each [[integer]] ''g'', there is a finite '''obstruction set''' of graphs <math>L(g) = \left\{G_{i}^{(g)}\right\}</math> such that a graph ''H'' is [[graph embedding|embeddable]] on a surface of [[Genus (mathematics)|genus]] ''g'' if and only if ''H'' contains no homeomorphic copy of any of the <math>G_{i}^{(g)\!}</math>.  For example, <math>L(0) = \left\{K_{5}, K_{3,3}\right\}</math> consists of the Kuratowski subgraphs.

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

{{multiple image
| align       = none
| total_width = 300
| image1      = Graph homeomorphism example 1.svg
| caption1    = Graph ''G''
| image2      = Graph homeomorphism example 2.svg
| caption2    = 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:

{{multiple image
| align       = none
| total_width = 150
| image1      = Graph homeomorphism example 3.svg
| caption1    = Graph ''G′'', ''H′''
}}

Therefore, there exists an isomorphism between ''<nowiki>G'</nowiki>'' and ''<nowiki>H'</nowiki>'', meaning ''G'' and ''H'' are homeomorphic.

===mixed graph===
The following [[Mixed graph|mixed graphs]] are homeomorphic. The directed edges are shown to have an intermediate arrow head.

{{multiple image
| align       = none
| total_width = 400
| image1      = Mixedgraph1.png
| caption1    = Graph ''G''
| image2      = Mixedgraph2.png
| caption2    = Graph ''H''
}}

==See also==
*[[Minor (graph theory)]]
*[[Edge contraction]]

==References==
<references />

==Further reading==
*{{Citation | last1=Yellen | first1=Jay | last2=Gross | first2=Jonathan L. | title=Graph Theory and Its Applications | publisher=Chapman & Hall/CRC | edition=2nd | series=Discrete Mathematics and Its Applications | isbn=978-1-58488-505-4 | year=2005}}

[[Category:Graph theory]]
[[Category:Homeomorphisms]]
[[Category:NP-complete problems]]