In topological graph theory, a 1-planar graph is a graph that can be drawn in the

Euclidean plane In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions ...

in such a way that each edge has at most one crossing point, where it crosses a single additional edge. If a 1-planar graph, one of the most natural generalizations of

planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...

s, is drawn that way, the drawing is called a 1-plane graph or 1-planar embedding of the graph.

Coloring

1-planar graphs were first studied by , who showed that they can be

colored ''Colored'' (or ''coloured'') is a racial descriptor historically used in the United States during the Jim Crow Era to refer to an African American. In many places, it may be considered a slur, though it has taken on a special meaning in Sout ...

with at most seven colors. Later, the precise number of colors needed to color these graphs, in the worst case, was shown to be six.. The example of the

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...

''K''₆, which is 1-planar, shows that 1-planar graphs may sometimes require six colors. However, the proof that six colors are always enough is more complicated. Prism-vf-color

Ringel's motivation was in trying to solve a variation of

total coloring In graph theory, total coloring is a type of graph coloring on the vertices and edges of a graph. When used without any qualification, a total coloring is always assumed to be ''proper'' in the sense that no adjacent edges, no adjacent vertices ...

for

s, in which one simultaneously colors the vertices and faces of a planar graph in such a way that no two adjacent vertices have the same color, no two adjacent faces have the same color, and no vertex and face that are adjacent to each other have the same color. This can obviously be done using eight colors by applying the

four color theorem In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions sha ...

to the given graph and its dual graph separately, using two disjoint sets of four colors. However, fewer colors may be obtained by forming an auxiliary graph that has a vertex for each vertex or face of the given planar graph, and in which two auxiliary graph vertices are adjacent whenever they correspond to adjacent features of the given planar graph. A vertex coloring of the auxiliary graph corresponds to a vertex-face coloring of the original planar graph. This auxiliary graph is 1-planar, from which it follows that Ringel's vertex-face coloring problem may also be solved with six colors. The graph ''K''₆ cannot be formed as an auxiliary graph in this way, but nevertheless the vertex-face coloring problem also sometimes requires six colors; for instance, if the planar graph to be colored is a

triangular prism In geometry, a triangular prism is a three-sided prism; it is a polyhedron made of a triangular base, a translated copy, and 3 faces joining corresponding sides. A right triangular prism has rectangular sides, otherwise it is ''oblique''. A ...

, then its eleven vertices and faces require six colors, because no three of them may be given a single color.

Edge density

Every 1-planar graph with ''n'' vertices has at most 4''n'' − 8 edges. More strongly, each 1-planar drawing has at most ''n'' − 2 crossings; removing one edge from each crossing pair of edges leaves a planar graph, which can have at most 3''n'' − 6 edges, from which the 4''n'' − 8 bound on the number of edges in the original 1-planar graph immediately follows. However, unlike planar graphs (for which all maximal planar graphs on a given vertex set have the same number of edges as each other), there exist maximal 1-planar graphs (graphs to which no additional edges can be added while preserving 1-planarity) that have significantly fewer than 4''n'' − 8 edges. The bound of 4''n'' − 8 on the maximum possible number of edges in a 1-planar graph can be used to show that the

''K''₇ on seven vertices is not 1-planar, because this graph has 21 edges and in this case 4''n'' − 8 = 20 < 21. A 1-planar graph is said to be an optimal 1-planar graph if it has exactly 4''n'' − 8 edges, the maximum possible. In a 1-planar embedding of an optimal 1-planar graph, the uncrossed edges necessarily form a quadrangulation (a polyhedral graph in which every face is a

quadrilateral In geometry a quadrilateral is a four-sided polygon, having four edges (sides) and four corners (vertices). The word is derived from the Latin words ''quadri'', a variant of four, and ''latus'', meaning "side". It is also called a tetragon, ...

). Every quadrangulation gives rise to an optimal 1-planar graph in this way, by adding the two diagonals to each of its quadrilateral faces. It follows that every optimal 1-planar graph is Eulerian (all of its vertices have even degree), that the minimum degree in such a graph is six, and that every optimal 1-planar graph has at least eight vertices of degree exactly six. Additionally, every optimal 1-planar graph is 4-vertex-connected, and every 4-vertex cut in such a graph is a separating cycle in the underlying quadrangulation. The graphs that have straight 1-planar drawings (that is, drawings in which each edge is represented by a line segment, and in which each line segment is crossed by at most one other edge) have a slightly tighter bound of 4''n'' − 9 on the maximum number of edges, achieved by infinitely many graphs.

Complete multipartite graphs

A complete classification of the 1-planar

complete bipartite graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory i ...

s, and more generally

complete multipartite graph In graph theory, a part of mathematics, a -partite graph is a graph whose vertices are (or can be) partitioned into different independent sets. Equivalently, it is a graph that can be colored with colors, so that no two endpoints of an edge ...

s is known. Every complete bipartite graph of the form ''K''_2,''n'' is 1-planar, as is every complete tripartite graph of the form ''K''_1,1,''n''. Other than these infinite sets of examples, the only complete multipartite 1-planar graphs are ''K''₆, ''K''_1,1,1,6, ''K''_1,1,2,3, ''K''_2,2,2,2, ''K''_1,1,1,2,2, and their subgraphs. The minimal non-1-planar complete multipartite graphs are ''K''_3,7, ''K''_4,5, ''K''_1,3,4, ''K''_2,3,3, and ''K''_1,1,1,1,3. For instance, the complete bipartite graph ''K''_3,6 is 1-planar because it is a subgraph of ''K''_1,1,1,6, but ''K''_3,7 is not 1-planar..

Computational complexity

It is

NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying ...

to test whether a given graph is 1-planar,. and it remains NP-complete even for the graphs formed from

s by adding a single edge and for graphs of bounded bandwidth.. The problem is

fixed-parameter tractable In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. T ...

when parameterized by cyclomatic number or by

tree-depth In graph theory, the tree-depth of a connected undirected graph G is a numerical invariant of G, the minimum height of a Trémaux tree for a supergraph of G. This invariant and its close relatives have gone under many different names in the lite ...

, so it may be solved in

polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

when those parameters are bounded. In contrast to Fáry's theorem for planar graphs, not every 1-planar graph may be drawn 1-planarly with straight

line segment In geometry, a line segment is a part of a straight line that is bounded by two distinct end points, and contains every point on the line that is between its endpoints. The length of a line segment is given by the Euclidean distance between i ...

s for its edges. However, testing whether a 1-planar drawing may be straightened in this way can be done in

. Additionally, every 3-vertex-connected 1-planar graph has a 1-planar drawing in which at most one edge, on the outer face of the drawing, has a bend in it. This drawing can be constructed in

linear time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

from a 1-planar embedding of the graph. The 1-planar graphs have bounded book thickness, but some 1-planar graphs including ''K''_2,2,2,2 have book thickness at least four.. 1-planar graphs have bounded local treewidth, meaning that there is a (linear) function ''f'' such that the 1-planar graphs of diameter ''d'' have

treewidth In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The gra ...

at most ''f''(''d''); the same property holds more generally for the graphs that can be embedded onto a surface of bounded genus with a bounded number of crossings per edge. They also have separators, small sets of vertices the removal of which decomposes the graph into connected components whose size is a constant fraction of the size of the whole graph. Based on these properties, numerous algorithms for planar graphs, such as Baker's technique for designing

approximation algorithm In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned sol ...

s, can be extended to 1-planar graphs. For instance, this method leads to a polynomial-time approximation scheme for the

maximum independent set In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set S of vertices such that for every two vertices in S, there is no edge connecting the tw ...

of a 1-planar graph.

Generalizations and related concepts

The class of graphs analogous to outerplanar graphs for 1-planarity are called the outer-1-planar graphs. These are graphs that can be drawn in a disk, with the vertices on the boundary of the disk, and with at most one crossing per edge. These graphs can always be drawn (in an outer-1-planar way) with straight edges and right angle crossings. By using

dynamic programming Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. ...

on the

SPQR tree In graph theory, a branch of mathematics, the triconnected components of a biconnected graph are a system of smaller graphs that describe all of the 2-vertex cuts in the graph. An SPQR tree is a tree data structure used in computer science, and ...

of a given graph, it is possible to test whether it is outer-1-planar in

.. The triconnected components of the graph (nodes of the SPQR tree) can consist only of

cycle graph In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...

s, bond graphs, and four-vertex

s, from which it also follows that outer-1-planar graphs are planar and have

at most three. The 1-planar graphs include the 4- map graphs, graphs formed from the adjacencies of regions in the plane with at most four regions meeting in any point. Conversely, every optimal 1-planar graph is a 4-map graph. However, 1-planar graphs that are not optimal 1-planar may not be map graphs. 1-planar graphs have been generalized to ''k''-planar graphs, graphs for which each edge is crossed at most ''k'' times (0-planar graphs are exactly the planar graphs). Ringel defined the local crossing number of ''G'' to be the least non-negative integer ''k'' such that ''G'' has a ''k''-planar drawing. Because the local crossing number is the maximum degree of the

intersection graph In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types o ...

of the edges of an optimal drawing, and the thickness (minimum number of planar graphs into which the edges can be partitioned) can be seen as the

chromatic number In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices ...

of an intersection graph of an appropriate drawing, it follows from

Brooks' theorem In graph theory, Brooks' theorem states a relationship between the maximum degree of a graph and its chromatic number. According to the theorem, in a connected graph in which every vertex has at most Δ neighbors, the vertices can be colored with ...

that the thickness is at most one plus the local crossing number. The ''k''-planar graphs with ''n'' vertices have at most ''O''(''k''^1/2''n'') edges, and treewidth ''O''((''kn'')^1/2). A

shallow minor In graph theory, a shallow minor or limited-depth minor is a restricted form of a graph minor in which the subgraphs that are contracted to form the minor have small diameter. Shallow minors were introduced by , who attributed their invention to ...

of a ''k''-planar graph, with depth ''d'', is itself a (2''d'' + 1)''k''-planar graph, so the shallow minors of 1-planar graphs and of ''k''-planar graphs are also sparse graphs, implying that the 1-planar and ''k''-planar graphs have

bounded expansion In graph theory, a family of graphs is said to have bounded expansion if all of its shallow minors are sparse graphs. Many natural families of sparse graphs have bounded expansion. A closely related but stronger property, polynomial expansion, i ...

.. Nonplanar graphs may also be parameterized by their crossing number, the minimum number of pairs of edges that cross in any drawing of the graph. A graph with crossing number ''k'' is necessarily ''k''-planar, but not necessarily vice versa. For instance, the

Heawood graph Heawood is a surname. Notable people with the surname include: * Jonathan Heawood, British journalist *Percy John Heawood (1861–1955), British mathematician **Heawood conjecture ** Heawood graph **Heawood number In mathematics, the Heawood numbe ...

has crossing number 3, but it is not necessary for its three crossings to all occur on the same edge of the graph, so it is 1-planar, and can in fact be drawn in a way that simultaneously optimizes the total number of crossings and the crossings per edge. Another related concept for nonplanar graphs is graph skewness, the minimal number of edges that must be removed to make a graph planar.

Coloring

Edge density

Complete multipartite graphs

Computational complexity

Generalizations and related concepts

References

Further reading