TOPICS
Search

Graph Planarization


The graph planarization of a graph drawing in the plane with finitely many graph crossings is the planar graph obtained by making each graph crossing a new graph vertex and splitting the edges at those points. In a good graph drawing, each new graph vertex has vertex degree 4.

For n>=4, every good graph 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