Editing Homeomorphism (graph theory) (section)

==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]].