TOPICS
Search

k-Planar Graph

A k-planar graph is a graph in which each edge is allowed to be crossed at most k times.

The least nonnegative integer k such that a graph has a k-planar drawing is known as its local crossing number.

See also

1-Planar Graph, 2-Planar Graph, Local Crossing Number

Explore with Wolfram|Alpha

References

Bekos, M. A.; Kaufmann, M.; and Raftopoulou, C. N. "On Optimal 2- and 3-Planar Graphs." In SoCG 2017 (Ed. B. Aronov and M. J. Katz). Vol. 77 of LIPIcs, Schloss Dagstuhl--Leibniz-Zentrum für Informatik, pp. 16:1-16:16, 2017.Pach, J. and Tóth, G. "Graphs Drawn With Few Crossings Per Edge." Combinatorica 17, 427-439, 1997.Pach, J.; Radoičić, R.; Tardos, G.; and Tóth, G. "Improving the Crossing Lemma by Finding More Crossings in Sparse Graphs." Disc. Comput. Geom. 36, 527-552, 2006.

Cite this as:

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