In topological graph theory, a 1-planar graph is a graph that can be drawn in the Euclidean plane 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 graphs, is drawn that way, the drawing is called a 1-plane graph or 1-planar embedding of the graph.
1-planar graphs were first studied by Ringel (1965), who showed that they can be colored with at most seven colors. [1] Later, the precise number of colors needed to color these graphs, in the worst case, was shown to be six. [2] The example of the complete graph K6, 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.
Ringel's motivation was in trying to solve a variation of total coloring for planar graphs, 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 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. [2] The graph K6 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, then its eleven vertices and faces require six colors, because no three of them may be given a single color. [3]
Every 1-planar graph with n vertices has at most 4n − 8 edges. [4] 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 3n − 6 edges, from which the 4n − 8 bound on the number of edges in the original 1-planar graph immediately follows. [5] 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 4n − 8 edges. [6] The bound of 4n − 8 on the maximum possible number of edges in a 1-planar graph can be used to show that the complete graph K7 on seven vertices is not 1-planar, because this graph has 21 edges and in this case 4n − 8 = 20 < 21. [7]
A 1-planar graph is said to be an optimal 1-planar graph if it has exactly 4n − 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). 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. [8]
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 4n − 9 on the maximum number of edges, achieved by infinitely many graphs. [9]
A complete classification of the 1-planar complete graphs, complete bipartite graphs, and more generally complete multipartite graphs is known. Every complete bipartite graph of the form K2,n is 1-planar (even planar), as is every complete tripartite graph of the form K1,1,n. Other than these infinite sets of examples, the only complete multipartite 1-planar graphs are K6, K1,1,1,6, K1,1,2,3, K2,2,2,2, K1,1,1,2,2, and their subgraphs. The minimal non-1-planar complete multipartite graphs are K3,7, K4,5, K1,3,4, K2,3,3, and K1,1,1,1,3. For instance, the complete bipartite graph K3,6 is 1-planar because it is a subgraph of K1,1,1,6, but K3,7 is not 1-planar. [7]
It is NP-complete to test whether a given graph is 1-planar, [10] [11] and it remains NP-complete even for the graphs formed from planar graphs by adding a single edge [12] and for graphs of bounded bandwidth. [13] The problem is fixed-parameter tractable when parameterized by cyclomatic number or by tree-depth, so it may be solved in polynomial time when those parameters are bounded. [13]
In contrast to Fáry's theorem for planar graphs, not every 1-planar graph may be drawn 1-planarly with straight line segments for its edges. [14] [15] However, testing whether a 1-planar drawing may be straightened in this way can be done in polynomial time. [16] 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 from a 1-planar embedding of the graph. [17] The 1-planar graphs have bounded book thickness, [18] but some 1-planar graphs including K2,2,2,2 have book thickness at least four. [19]
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 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 algorithms, can be extended to 1-planar graphs. For instance, this method leads to a polynomial-time approximation scheme for the maximum independent set of a 1-planar graph. [20]
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. [21] By using dynamic programming on the SPQR tree of a given graph, it is possible to test whether it is outer-1-planar in linear time. [22] [23] The triconnected components of the graph (nodes of the SPQR tree) can consist only of cycle graphs, bond graphs, and four-vertex complete graphs, from which it also follows that outer-1-planar graphs are planar and have treewidth 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. [24]
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 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 of an intersection graph of an appropriate drawing, it follows from Brooks' theorem that the thickness is at most one plus the local crossing number. [25] The k-planar graphs with n vertices have at most O(k1/2n) edges, [26] and treewidth O((kn)1/2). [27] A shallow minor of a k-planar graph, with depth d, is itself a (2d + 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. [28]
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 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.
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 cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.
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 connected by a pair of unique edges.
In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.
In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges, vertices and by contracting edges.
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 a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.
In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.
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 graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly k are called k-trees, and the graphs with treewidth at most k are called partial k-trees. Many other well-studied graph families also have bounded treewidth.
In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings in a book, a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie on this boundary line, called the spine, and the edges are required to stay within a single half-plane. The book thickness of a graph is the smallest possible number of half-planes for any book embedding of the graph. Book thickness is also called pagenumber, stacknumber or fixed outerthickness. Book embeddings have also been used to define several other graph invariants including the pagewidth and book crossing number.
In graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph, and the pathwidth of G is a number that measures how much the path was thickened to form G. More formally, a path-decomposition is a sequence of subsets of vertices of G such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as interval thickness, vertex separation number, or node searching number.
In graph theory, a branch of mathematics, a clique sum is a way of combining two graphs by gluing them together at a clique, analogous to the connected sum operation in topology. If two graphs G and H each contain cliques of equal size, the clique-sum of G and H is formed from their disjoint union by identifying pairs of vertices in these two cliques to form a single shared clique, and then deleting all the clique edges or possibly deleting some of the clique edges. A k-clique-sum is a clique-sum in which both cliques have exactly k vertices. One may also form clique-sums and k-clique-sums of more than two graphs, by repeated application of the clique-sum operation.
In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle. The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none of its edges cross, and the cycle connects the leaves in their clockwise ordering in this embedding. Thus, the cycle forms the outer face of the Halin graph, with the tree inside it.
In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. It is an apex, not the apex because an apex graph may have more than one apex; for example, in the minimal nonplanar graphs K5 or K3,3, every vertex is an apex. The apex graphs include graphs that are themselves planar, in which case again every vertex is an apex. The null graph is also counted as an apex graph even though it has no vertex to remove.
In combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles. Apollonian networks may equivalently be defined as the planar 3-trees, the maximal planar chordal graphs, the uniquely 4-colorable planar graphs, and the graphs of stacked polytopes. They are named after Apollonius of Perga, who studied a related circle-packing construction.
In graph drawing, the angular resolution of a drawing of a graph is the sharpest angle formed by any two edges that meet at a common vertex of the drawing.
In graph drawing, a RAC drawing of a graph is a drawing in which the vertices are represented as points, the edges are represented as straight line segments or polylines, at most two edges cross at any point, and when two edges cross they do so at right angles to each other. In the name of this drawing style, "RAC" stands for "right angle crossing".
In the mathematical field of graph theory, planarization is a method of extending graph drawing methods from planar graphs to graphs that are not planar, by embedding the non-planar graphs within a larger planar graph.
In graph drawing, the area used by a drawing is a commonly used way of measuring its quality.
In the mathematical field of graph theory, the queue number of a graph is a graph invariant defined analogously to stack number using first-in first-out (queue) orderings in place of last-in first-out (stack) orderings.
In graph theory, a k-outerplanar graph is a planar graph that has a planar embedding in which the vertices belong to at most concentric layers. The outerplanarity index of a planar graph is the minimum value of for which it is -outerplanar.
In graph theory, the cutwidth of an undirected graph is the smallest integer with the following property: there is an ordering of the vertices of the graph, such that every cut obtained by partitioning the vertices into earlier and later subsets of the ordering is crossed by at most edges. That is, if the vertices are numbered , then for every , the number of edges with and is at most .