Subdivision (graph theory)

In graph theory, two graphs $G$ and $G'$ are homeomorphic if there is a graph isomorphism from some subdivision of $G$ to some subdivision of $G'$. If the edges of a graph are thought of as lines drawn from one 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 homeomorphic in the topological sense.

Subdivision and smoothing

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 yields a graph containing one new vertex ''w'', and with an edge set replacing ''e'' by two new edges, and . For directed edges, this operation shall preserve their propagating direction.

For example, the edge ''e'', with endpoints :

can be subdivided into two edges, ''e''₁ and ''e''₂, connecting to a new vertex ''w'' of degree-2, or indegree-1 and outdegree-1 for the directed edge:

Determining whether for graphs ''G'' and ''H'', ''H'' is homeomorphic to a subgraph of ''G'', is an NP-complete problem.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. .

Reversion

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

For example, the simple connected graph with two edges, ''e''₁ and ''e''₂ :

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

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''^th 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 planarity. Kuratowski's theorem states that
: a finite graph is planar if and only if it contains no subgraph homeomorphic to ''K''₅ ( complete graph on five vertices) or ''K''_3,3 ( complete bipartite graph on six vertices, three of which connect to each of the other three).

In fact, a graph homeomorphic to ''K''₅ or ''K''_3,3 is called a Kuratowski subgraph.

A generalization, following from the Robertson–Seymour theorem, asserts that for each integer ''g'', there is a finite obstruction set of graphs $L(g) = \left\$ such that a graph ''H'' is embeddable on a surface of genus ''g'' if and only if ''H'' contains no homeomorphic copy of any of the $G_^$. For example, $L(0) = \left\$ consists of the Kuratowski subgraphs.

Example

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

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:

Therefore, there exists an isomorphism between ''G''' and ''H''', meaning ''G'' and ''H'' are homeomorphic.

mixed graph

The following mixed graphs are homeomorphic. The directed edges are shown to have an intermediate arrow head.

See also

* Minor (graph theory)
* Edge contraction

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

Graph theory
Homeomorphisms
NP-complete problems