TOPICS
Search

1-Planar Graph


A 1-planar graph is a graph that can be drawn in the plane such that each edge has at most one crossing point at which it crosses a single additional edge (Ringel 1965).

A 1-planar graph with n vertices has at most 4n-8 edges. Such optimal 1-planar graphs have been completely characterized.

4-map graphs are 1-planar.

Fabrici and Madaras (2007) showed that that a 1-planar graph has minimum vertex degree delta<=7 and that every 3-connected 1-planar graph contains an edge with both endvertices of degrees at most 20.

Borodin (1984) proved that 1-planar graphs are 6-colorable (Fabrici and Madara 2007).

A 1-planar drawing has at most n-2 crossings.


See also

2-Planar Graph, Singlecross Graph

Explore with Wolfram|Alpha

References

Borodin, O. V. "Solution of Ringel's Problems on the Vertex-Face Coloring of Plane Graphs and on the Coloring of 1-Planar Graphs." Diskret. Anal. Novosibirsk 41, 12-26, 1984.Brandenburg, F. J. "Straight-Line Drawings of 1-Planar Graphs." 3 Sep 2021. https://arxiv.org/abs/2109.01692.Fabrici, I. and Madaras, T. "The Structure of 1-Planar Graphs." Disc. Math. 307, 854-865, 2007.Ringel, G. "Ein Sechsfarbenproblem auf der Kugel." Abh. Math. Sem. Univ. Hamburg 29, 107-117, 1965.

Cite this as:

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