TOPICS
Search

Graph Planarization


The graph planarization of a graph drawing in the plane, whose edges meet away from vertices only at finitely many crossing points, is the planar graph obtained by making each crossing point a new graph vertex and splitting the edges at those points. In a good drawing, each new graph vertex has vertex degree 4.

For n>=4, every good drawing in the plane of the complete graph K_n has a 3-connected graph planarization (Pan and Richter 2007). Here, good means that adjacent edges meet only at their common endpoint, independent edges meet at most once and only transversely, and no three edges meet away from vertices.


See also

Graph Crossing, Graph Crossing Number, Graph Drawing, Planar Graph

Explore with Wolfram|Alpha

References

Pan, S. and Richter, R. B. "The Crossing Number of K_(11) Is 100." J. Graph Th. 56, 128-134, 2007. https://doi.org/10.1002/jgt.20249.

Cite this as:

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

Subject classifications