1-planar graph
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.
Coloring
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]
Edge density
Every 1-planar graph with n vertices has at most 4n − 8 edges.
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
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]
Complete multipartite graphs
A complete classification of the 1-planar
Computational complexity
It is
In contrast to
1-planar graphs have
The class of graphs analogous to
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
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
References
- S2CID 123286264.
- ^ MR 0832128.
- S2CID 1028234.
- MR 0847368.
- doi:10.37236/2392.
- ^ Brandenburg, Franz Josef; Eppstein, David; Gleißner, Andreas; Goodrich, Michael T.; Hanauer, Kathrin; Reislhuber, Josef (2013), "On the density of maximal 1-planar graphs", in Didimo, Walter; Patrignani, Maurizio (eds.), Proc. 20th Int. Symp. Graph Drawing.
- ^ MR 2876333.
- MR 2746706.
- MR 3017985.
- S2CID 8174422.
- S2CID 13436158.
- Bibcode:2012arXiv1203.5944C. Expanded version of a paper from the 17th ACM Symposium on Computational Geometry, 2010.
- ^ S2CID 4417962.
- MR 0846198.
- MR 0956195.
- .
- .
- .
- ^ Bekos, Michael; Kaufmann, Michael; Zielke, Christian (2015), "The book embedding problem from a SAT-solving perspective", Proc. 23rd International Symposium on Graph Drawing and Network Visualization (GD 2015), pp. 113–125.
- ^ Grigoriev & Bodlaender (2007). Grigoriev and Bodlaender state their results only for graphs with a known 1-planar embedding, and use a tree decomposition of a planarization of the embedding with crossings replaced by degree-four vertices; however, their methods straightforwardly imply bounded local treewidth of the original 1-planar graph, allowing Baker's method to be applied directly to it without knowing the embedding.
- MR 3042921.
- .
- .
- S2CID 2657838.
- S2CID 121667358.
- S2CID 20480170.
- Bibcode:2015arXiv150604380D.
- MR 2920058.
Further reading
- Kobourov, Stephen; Liotta, Giuseppe; Montecchiani, Fabrizio (2017), "An annotated bibliography on 1-planarity", Computer Science Review, 25: 49–67, S2CID 7732463