TOPICS
Search

Edge Splitting


Edge splitting is the reverse of edge contraction. In a simple graph, it replaces a graph vertex w by adjacent vertices u and v and distributes the former neighbors of w between them, allowing a former neighbor to be adjacent to both. Contracting uv, deleting the resulting graph loop, and identifying parallel edges recovers the original graph.

Under this inverse-contraction convention, the d-dimensional operation of vertex splitting is a restricted edge split, with exactly d-1 common neighbors of the two new vertices. The terminology is not uniform. In rigidity theory, "edge splitting" also denotes the different operation that deletes an graph edge ab and adds a new graph vertex joined to a, b, and d-1 other vertices (Schulze and Whiteley 2017, pp. 1597-1599). That operation splits an graph edge, whereas vertex splitting splits an existing graph vertex.


See also

Edge Contraction, Vertex Splitting

Portions of this entry contributed by Ed Pegg, Jr. (author's link)

Explore with Wolfram|Alpha

References

Schulze, B. and Whiteley, W. "Rigidity and Scene Analysis." In Handbook of Discrete and Computational Geometry, 3rd ed. (Ed. C. D. Tóth, J. O'Rourke, and J. E. Goodman). Boca Raton, FL: CRC Press, pp. 1593-1632, 2017. https://www.csun.edu/~ctoth/Handbook/chap61.pdf.

Referenced on Wolfram|Alpha

Edge Splitting

Cite this as:

Weisstein, Eric W., with contributions by Ed Pegg, Jr.. "Edge Splitting." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/EdgeSplitting.html

Subject classifications