1-planar graph

Graph with at most one crossing per edge thumb|A 1-planar drawing of the Heawood graph: six of the edges have a single crossing, and the remaining 15 edges are not crossed. 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. Ringel Gerhard Gerhard Ringel 10.1007/BF02996313 Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg German 0187232 107–117 Ein Sechsfarbenproblem auf der Kugel 29 1965 1–2 123286264 . Later, the precise number of colors needed to color these graphs, in the worst case, was shown to be six. Borodin O. V. 41 Metody Diskretnogo Analiza 832128 12–26, 108 Solution of the Ringel problem on vertex-face coloring of planar graphs and coloring of 1-planar graphs 1984. 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. thumb|left|Coloring the vertices and faces of the triangular prism graph requires six colors 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. 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. Albertson Michael O. Mohar Bojan Bojan Mohar 10.1007/s00373-006-0653-4 3 Graphs and Combinatorics 2264852 289–295 Coloring vertices and faces of locally planar graphs http://www.fmf.uni-lj.si/~mohar/Reprints/2006/BM06_GC22_Albertson_ColoringPlanarGraphs.pdf 22 2006 1028234 . Edge density Every 1-planar graph with n vertices has at most 4n − 8 edges. Schumacher H. Mathematische Nachrichten German 847368 291–300 Zur Struktur 1-planarer Graphen 125 1986 10.1002/mana.19861250122 . 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.On drawings and decompositions of 1-planar graphs Július Czap Dávid Hudák Electronic Journal of Combinatorics 2013 20 2 10.37236/2392 P54 http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i2p54 free. 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. Brandenburg Franz Josef Eppstein David David Eppstein Gleißner Andreas Goodrich Michael T. Michael T. Goodrich Hanauer Kathrin Reislhuber Josef Didimo Walter Patrignani Maurizio On the density of maximal 1-planar graphs Proc. 20th Int. Symp. Graph Drawing 2013. 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. 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. Suzuki Yusuke 10.1137/090746835 4 SIAM Journal on Discrete Mathematics 2746706 1527–1540 Re-embeddings of maximum 1-planar graphs 24 2010. 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. Didimo Walter 10.1016/j.ipl.2013.01.013 7 Information Processing Letters 3017985 236–240 Density of straight-line 1-planar graph drawings 113 2013. Complete multipartite graphs thumb|300px|1-planar drawing of the cocktail party graph K2,2,2,2 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. Czap Július Hudák Dávid 10.1016/j.dam.2011.11.014 4–5 Discrete Applied Mathematics 2876333 505–512 1-planarity of complete multipartite graphs 160 2012 . Computational complexity It is NP-complete to test whether a given graph is 1-planar, Grigoriev Alexander Bodlaender Hans L. Hans L. Bodlaender 10.1007/s00453-007-0010-x 1 Algorithmica 2344391 1–11 Algorithms for graphs embeddable with few crossings per edge 49 2007 1874/17980 8174422 https://cris.maastrichtuniversity.nl/en/publications/5984fed8-f0b5-4b0d-91fe-2ca15d158421 free . Korzhik Vladimir P. Mohar Bojan Bojan Mohar Tollis Ioannis G. Patrignani Maurizio Minimal obstructions for 1-immersions and hardness of 1-planarity testing 10.1007/978-3-642-00219-9_29 302–312 Springer Lecture Notes in Computer Science Graph Drawing: 16th International Symposium, GD 2008, Heraklion, Crete, Greece, September 21-24, 2008, Revised Papers 5417 2009 1110.4881 978-3-642-00218-2 13436158 . and it remains NP-complete even for the graphs formed from planar graphs by adding a single edge Sergio Cabello Mohar Bojan Bojan Mohar Adding one edge to planar graphs makes crossing number and 1-planarity hard 2012 1203.5944 2012arXiv1203.5944C . Expanded version of a paper from the 17th ACM Symposium on Computational Geometry, 2010. and for graphs of bounded bandwidth.Parameterized complexity of 1-planarity Michael J. Bannister Sergio Cabello David Eppstein David Eppstein Algorithms and Data Structures Symposium (WADS 2013) 2013 22 23–49 10.7155/jgaa.00457 free 1304.5591 2013arXiv1304.5591B 4417962. 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. 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. Eggleton Roger B. Utilitas Mathematica 846198 149–172 Rectilinear drawings of graphs 29 1986. Thomassen Carsten Carsten Thomassen (mathematician) 10.1002/jgt.3190120306 3 Journal of Graph Theory 956195 335–341 Rectilinear drawings of graphs 12 1988. However, testing whether a 1-planar drawing may be straightened in this way can be done in polynomial time. Hong Seok-Hee Seok-Hee Hong Eades Peter Peter Eades Liotta Giuseppe Poon Sheung-Hung Gudmundsson Joachim Mestre Julián Viglas Taso Fáry's theorem for 1-planar graphs 10.1007/978-3-642-32241-9_29 335–346 Springer Lecture Notes in Computer Science Computing and Combinatorics: 18th Annual International Conference, COCOON 2012, Sydney, Australia, August 20-22, 2012, Proceedings 7434 2012 978-3-642-32240-2 . 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. Alam Md. Jawaherul Brandenburg Franz J. Kobourov Stephen G. Straight-line grid drawings of 3-connected 1-planar graphs 10.1007/978-3-319-03841-4_8 83–94 Lecture Notes in Computer Science Graph Drawing: 21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers http://www.cs.arizona.edu/~mjalam/straight_1_planar_3_connected.pdf 8242 2013 free 978-3-319-03840-7 . The 1-planar graphs have bounded book thickness, Bekos Michael A. Bruckdorfer Till Kaufmann Michael Raftopoulou Chrysanthi 1-Planar graphs have constant book thickness 10.1007/978-3-662-48350-3_12 130–141 Springer Lecture Notes in Computer Science Algorithms – ESA 2015 9294 2015 978-3-662-48349-7 . but some 1-planar graphs including K2,2,2,2 have book thickness at least four.The book embedding problem from a SAT-solving perspective Michael Bekos Michael Kaufmann Christian Zielke 113–125 Proc. 23rd International Symposium on Graph Drawing and Network Visualization (GD 2015) 2015. 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.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. 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. Dehkordi Hooman Reisi Eades Peter Peter Eades 10.1142/S021819591250015X 6 International Journal of Computational Geometry & Applications 3042921 543–557 Every outer-1-plane graph has a right angle crossing drawing 22 2012. 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. Hong Seok-Hee Seok-Hee Hong Eades Peter Peter Eades Katoh Naoki Liotta Giuseppe Schweitzer Pascal Suzuki Yusuke Wismath Stephen Wolff Alexander A linear-time algorithm for testing outer-1-planarity 10.1007/978-3-319-03841-4_7 71–82 Lecture Notes in Computer Science 21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers 8242 2013 free 978-3-319-03840-7 . Auer Christopher Bachmaier Christian Brandenburg Franz J. Gleißner Andreas Hanauer Kathrin Neuwirth Daniel Reislhuber Josef Wismath Stephen Wolff Alexander Recognizing outer 1-planar graphs in linear time 10.1007/978-3-319-03841-4_10 107–118 Lecture Notes in Computer Science 21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers 8242 2013 free 978-3-319-03840-7 . 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. Chen Zhi-Zhong Grigni Michelangelo Papadimitriou Christos H. Christos Papadimitriou 10.1145/506147.506148 2 Journal of the ACM 2147819 127–138 Map graphs 49 2002 cs/9910013 2657838 . 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. Kainen Paul Paul Chester Kainen 10.1007/BF02992822 Abh. Math. Sem. Univ. Hamburg 0335322 88–95 Thickness and coarseness of graphs 39 1973 121667358 . The k-planar graphs with n vertices have at most O(k1/2n) edges, Pach János János Pach Tóth Géza 10.1007/BF01215922 3 Combinatorica 1606052 427–439 Graphs drawn with few crossings per edge 17 1997 20480170 http://infoscience.epfl.ch/record/129201 . and treewidth O((kn)1/2).Genus, treewidth, and local crossing number Vida Dujmović Vida Dujmović David Eppstein David Eppstein David R. Wood David Wood (mathematician) 77–88 Proc. 23rd International Symposium on Graph Drawing and Network Visualization (GD 2015) 2015 1506.04380 2015arXiv150604380D. 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. Nešetřil Jaroslav Jaroslav Nešetřil Ossona de Mendez Patrice Patrice Ossona de Mendez 10.1007/978-3-642-27875-4 978-3-642-27874-7 2920058 Theorem 14.4, p. 321 Springer Algorithms and Combinatorics Sparsity: Graphs, Structures, and Algorithms 28 2012 . 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. References 30em Further reading Kobourov Stephen Liotta Giuseppe Montecchiani Fabrizio 1703.02261 An annotated bibliography on 1-planarity Computer Science Review 2017 25 49–67 10.1016/j.cosrev.2017.06.002 2017arXiv170302261K 7732463 Category:Planar graphs Category:NP-complete problems