In
graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, two
graphs and
are homeomorphic if there is a
graph isomorphism
In graph theory, an isomorphism of graphs ''G'' and ''H'' is a bijection between the vertex sets of ''G'' and ''H''
: f \colon V(G) \to V(H)
such that any two vertices ''u'' and ''v'' of ''G'' are adjacent in ''G'' if and only if f(u) and f(v) a ...
from some
subdivision
Subdivision may refer to:
Arts and entertainment
* Subdivision (metre), in music
* ''Subdivision'' (film), 2009
* "Subdivision", an episode of ''Prison Break'' (season 2)
* ''Subdivisions'' (EP), by Sinch, 2005
* "Subdivisions" (song), by Rush ...
of
to some subdivision of
. 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 mathematics and more specifically in topology, a homeomorphism ( from Greek roots meaning "similar shape", named by Henri Poincaré), also called topological isomorphism, or bicontinuous function, is a bijective and continuous function betw ...
in the
topological
Topology (from the Greek words , and ) is the branch of mathematics concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, wit ...
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''
1 and ''e''
2, 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
In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''.
Somewhat more precisely, a problem is NP-complete when:
# It is a decision problem, meaning that for any ...
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
In the mathematics, mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path (graph theory), path in an undirected or directed graph that visits each vertex (graph theory), vertex exactly once. A Hamiltonian cycle (or ...
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''
1, ''e''
2) incident on ''w'', removes both edges containing ''w'' and replaces (''e''
1, ''e''
2) 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''
1 and ''e''
2 :
has a vertex (namely ''w'') that can be smoothed away, resulting in:
Barycentric subdivisions
The
barycentric subdivision
In mathematics, the barycentric subdivision is a standard way to subdivide a given simplex into smaller ones. Its extension to simplicial complexes is a canonical method to refining them. Therefore, the barycentric subdivision is an important tool ...
subdivides each edge of the graph. This is a special subdivision, as it always results in a
bipartite graph
In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...
. 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
In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a Set (mathematics), set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called ''Ver ...
.
Embedding on a surface
It is evident that subdividing a graph preserves
planarity.
Kuratowski's theorem
In graph theory, Kuratowski's theorem is a mathematical forbidden graph characterization of planar graphs, named after Kazimierz Kuratowski. It states that a finite graph is planar if and only if it does not contain a Glossary of graph theory#Su ...
states that
: a
finite graph
In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...
is planar
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...
it contains no
subgraph homeomorphic to ''K''
5 (
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices i ...
on five vertices) or ''K''
3,3 (
complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17.
Graph theory ...
on six vertices, three of which connect to each of the other three).
In fact, a graph homeomorphic to ''K''
5 or ''K''
3,3 is called a
Kuratowski subgraph.
A generalization, following from the
Robertson–Seymour theorem
In graph theory, the Robertson–Seymour theorem (also called the graph minors theorem) states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering. Equivalently, every family of graphs that is ...
, asserts that for each
integer
An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
''g'', there is a finite obstruction set of graphs
such that a graph ''H'' is
embeddable on a surface of
genus
Genus (; : genera ) is a taxonomic rank above species and below family (taxonomy), family as used in the biological classification of extant taxon, living and fossil organisms as well as Virus classification#ICTV classification, viruses. In bino ...
''g'' if and only if ''H'' contains no homeomorphic copy of any of the
. For example,
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
Mixed is the past tense of ''mix''.
Mixed may refer to:
* Mixed (United Kingdom ethnicity category), an ethnicity category that has been used by the United Kingdom's Office for National Statistics since the 2001 Census Music
* ''Mixed'' (album) ...
are homeomorphic. The directed edges are shown to have an intermediate arrow head.
See also
*
Minor (graph theory)
Minor may refer to:
Common meanings
* Minor (law), a person not under the age of certain legal activities.
* Academic minor, a secondary field of study in undergraduate education
Mathematics
* Minor (graph theory), a relation of one graph to ...
*
Edge contraction
In graph theory, an edge contraction is an operation that removes an edge from a graph while simultaneously merging the two vertices that it previously joined. Edge contraction is a fundamental operation in the theory of graph minors. Vertex id ...
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