TOPICS
Search

Graph Subdivision


GraphSubdivision

An edge subdivision is the insertion of a new vertex v_j in the middle of an exiting edge e=v_iv_k accompanied by the joining of the original edge endpoints with the new vertex to form new edges e^'=v_iv_j and e^('')=v_jv_k (Gross and Yellen 2006, p. 293).

A graph subdivision is therefore a sequence of edge subdivisions.

Graphs for which there exists an isomorphism from a subdivision of one to a subdivision of the other are said to be homeomorphic graphs.

In general, a graph simple unlabeled graph whose connectivity is considered purely on the basis of topological equivalence (i.e., up to smoothing and subdivision) is known as a topological graph.

The opposite of graph subdivision is graph smoothing.


See also

Graph Smoothing, Homeomorphic Graphs, Topological Graph

Explore with Wolfram|Alpha

References

Gross, J. T. and Yellen, J. Graph Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, p. 293, 2006.

Cite this as:

Weisstein, Eric W. "Graph Subdivision." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GraphSubdivision.html

Subject classifications