In graph theory, two graphs and are homeomorphic if there is a graph isomorphism from some subdivision 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 illustrations), then two graphs are homeomorphic to each other in the graph-theoretic sense precisely if they are homeomorphic in the topological sense.[1]
In general, a subdivision of a graph G (sometimes known as an expansion[2]) 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 example, the edge e, with endpoints {u,v }:
can be subdivided into two edges, e1 and e2, connecting to a new vertex w:
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 degree-2 (i.e., 2-valent) vertices can be smoothed.
For example, the simple connected graph with two edges, e1 {u,w } and e2 {w,v }:
has a vertex (namely w) that can be smoothed away, resulting in:
Determining whether for graphs G and H, H is homeomorphic to a subgraph of G, is an NP-complete problem.[3]
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 nth 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 fact, a graph homeomorphic to K5 or K3,3 is called a Kuratowski subgraph.
A generalization, following from the Robertson–Seymour theorem, asserts that for each integerg, there is a finite obstruction set of graphs such that a graph H is embeddable on a surface of genusg 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.
Graph G
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:
Graph G′, H′
Therefore, there exists an isomorphism between G' and H', meaning G and H are homeomorphic.
^Archdeacon, Dan (1996), "Topological graph theory: a survey", Surveys in graph theory (San Francisco, CA, 1995), Congressus Numerantium, vol. 115, pp. 5–54, CiteSeerX10.1.1.28.1728, MR 1411236, The name arises because and are homeomorphic as graphs if and only if they are homeomorphic as topological spaces
^Trudeau, Richard J. (1993). Introduction to Graph Theory. Dover. p. 76. ISBN978-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.
^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, MR 0574589.
Further reading
Yellen, Jay; Gross, Jonathan L. (2005), Graph Theory and Its Applications, Discrete Mathematics and Its Applications (2nd ed.), Chapman & Hall/CRC, ISBN978-1-58488-505-4
February 13, 2023
homeomorphism, graph, theory, confused, with, graph, homomorphism, graph, theory, graphs, displaystyle, displaystyle, homeomorphic, there, graph, isomorphism, from, some, subdivision, displaystyle, some, subdivision, displaystyle, edges, graph, thought, lines,. Not to be confused with graph homomorphism In graph theory two graphs G displaystyle G and G displaystyle G are homeomorphic if there is a graph isomorphism from some subdivision of G displaystyle G to some subdivision of G displaystyle G If the edges of a graph are thought of as lines drawn from one vertex to another as they are usually depicted in illustrations then two graphs are homeomorphic to each other in the graph theoretic sense precisely if they are homeomorphic in the topological sense 1 Contents 1 Subdivision and smoothing 1 1 Barycentric subdivisions 2 Embedding on a surface 3 Example 4 See also 5 References 6 Further readingSubdivision and smoothing EditIn general a subdivision of a graph G sometimes known as an expansion 2 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 example the edge e with endpoints u v can be subdivided into two edges e1 and e2 connecting to a new vertex w 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 degree 2 i e 2 valent vertices can be smoothed For example the simple connected graph with two edges e1 u w and e2 w v has a vertex namely w that can be smoothed away resulting in Determining whether for graphs G and H H is homeomorphic to a subgraph of G is an NP complete problem 3 Barycentric subdivisions Edit 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 nth 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 EditIt 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 K5 complete graph on five vertices or K3 3 complete bipartite graph 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 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 G i g displaystyle L g left G i g right 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 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 Example EditIn the following example graph G and graph H are homeomorphic Graph G 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 Graph G H Therefore there exists an isomorphism between G and H meaning G and H are homeomorphic See also EditMinor graph theory Edge contractionReferences Edit 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 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 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 MR 0574589 Further reading EditYellen Jay Gross Jonathan L 2005 Graph Theory and Its Applications Discrete Mathematics and Its Applications 2nd ed Chapman amp Hall CRC ISBN 978 1 58488 505 4 Retrieved from https en wikipedia org w index php title Homeomorphism graph theory amp oldid 1136269637 Subdivision and smoothing, wikipedia, wiki, book, books, library,
