A Survey on Graph Drawing Beyond Planarity <s> EDGE DENSITY <s> Keywords: graphs drawn on plane ; crossing number Note: Professor Pach's number: [119]. Also in: Lecture Notes in Computer Science 1190, Springer-Verlag, Berlin, 1997, 345-354. Reference DCG-ARTICLE-1997-008doi:10.1007/BF01215922 Record created on 2008-11-14, modified on 2017-05-12 <s> BIB001 </s> A Survey on Graph Drawing Beyond Planarity <s> EDGE DENSITY <s> A geometric graph is a graph G = (V, E) drawn in the plane so that the vertex set V consists of points in general position and the edge set E consists of straight line segments between points of V. It is known that, for any fixed k, any geometric graph G on n vertices with no k pairwise crossing edges contains at most O(n log n) edges. In this paper we give a new, simpler proof of this bound, and show that the same bound holds also when the edges of G are represented by x-monotone curves (Jordan arcs). <s> BIB002 </s> A Survey on Graph Drawing Beyond Planarity <s> EDGE DENSITY <s> A {\em geometric graph\/} is a graph $G=(V,E)$ drawn in the plane so that the vertex set $V$ consists of points in general position and the edge set $E$ consists of straight line segments between points of $V$. Two edges of a geometric graph are said to be {\em parallel\/}, if they are opposite sides of a convex quadrilateral. In this paper we show that, for any fixed $k\ge3$, any geometric graph on $n$ vertices with no $k$ pairwise parallel edges contains at most $O(n)$ edges, and any geometric graph on $n$ vertices with no $k$ pairwise crossing edges contains at most $O(n\log n)$ edges. We also prove a conjecture of Kupitz that any geometric graph on $n$ vertices with no pair of parallel edges contains at most $2n-2$ edges. <s> BIB003 </s> A Survey on Graph Drawing Beyond Planarity <s> EDGE DENSITY <s> Let G be a topological graph on n vertices in the plane, i.e., a graph drawn in the plane with its vertices represented as points and its edges represented as Jordan arcs connecting pairs of points. It is shown that if no two edges of any cycle of length 4 in G cross an odd number of times, then |E(G)|=O(n8/5). <s> BIB004 </s> A Survey on Graph Drawing Beyond Planarity <s> EDGE DENSITY <s> Let G be a geometric graph with n vertices, i.e., a graph drawn in the plane with straight-line edges. It is shown that if G has no self-intersecting path of length 3, then its number of edges is O(n log n). This result is asymptotically tight. Analogous questions for longer forbidden paths and for graphs drawn by not necessarily straight-line edges are also considered. <s> BIB005 </s> A Survey on Graph Drawing Beyond Planarity <s> EDGE DENSITY <s> Twenty years ago, Ajtai et al. and, independently, Leighton discovered that the crossing number of any graph with v vertices and e > 4v edges is at least ce3/v2, where c > 0 is an absolute constant. This result, known as the "Crossing Lemma," has found many important applications in discrete and computational geometry. It is tight up to a multiplicative constant. Here we improve the best known value of the constant by showing that the result holds with c > 1024/31827 > 0.032. The proof has two new ingredients, interesting in their own right. We show that (1) if a graph can be drawn in the plane so that every edge crosses at most three others, then its number of edges cannot exceed 5.5(v-2); and (2) the crossing number of any graph is at least $\frac73e-\frac{25}3(v-2).$ Both bounds are tight up to an additive constant (the latter one in the range $4v\le e\le 5v$). <s> BIB006 </s> A Survey on Graph Drawing Beyond Planarity <s> EDGE DENSITY <s> A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. It is maximal 1-planar if the addition of any edge violates 1-planarity. ::: ::: Maximal 1-planar graphs have at most 4n−8 edges. We show that there are sparse maximal 1-planar graphs with only $\frac{45}{17} n + \mathcal{O}(1)$ edges. With a fixed rotation system there are maximal 1-planar graphs with only $\frac{7}{3} n + \mathcal{O}(1)$ edges. This is sparser than maximal planar graphs. There cannot be maximal 1-planar graphs with less than $\frac{21}{10} n - \mathcal{O}(1)$ edges and less than $\frac{28}{13} n - \mathcal{O}(1)$ edges with a fixed rotation system. Furthermore, we prove that a maximal 1-planar rotation system of a graph uniquely determines its 1-planar embedding. <s> BIB007 </s> A Survey on Graph Drawing Beyond Planarity <s> EDGE DENSITY <s> A topological graph is k-quasi-planar if it does not contain k pairwise crossing edges. An old conjecture states that for every fixed k, the maximum number of edges in a k-quasi-planar graph on n vertices is On. Fox and Pach showed that every k-quasi-planar graph with n vertices and no pair of edges intersecting in more than O1 points has at most nlogn Ologk edges. We improve this upper bound to $2^{\alphan^c}n\log n$ , where αn denotes the inverse Ackermann function, and c depends only on k. We also show that every k-quasi-planar graph with n vertices and every two edges have at most one point in common has at most Onlogn edges. This improves the previously known upper bound of $2^{\alphan^c}n\log n$ obtained by Fox, Pach, and Suk. <s> BIB008 </s> A Survey on Graph Drawing Beyond Planarity <s> EDGE DENSITY <s> A graph drawn in the plane with n vertices is k-fan-crossing free for k>1 if there are no k+1 edges $g,e_1,...e_k$, such that $e_1,e_2,...e_k$ have a common endpoint and $g$ crosses all $e_i$. We prove a tight bound of 4n-8 on the maximum number of edges of a 2-fan-crossing free graph, and a tight 4n-9 bound for a straight-edge drawing. For k>2, we prove an upper bound of 3(k-1)(n-2) edges. We also discuss generalizations to monotone graph properties. <s> BIB009 </s> A Survey on Graph Drawing Beyond Planarity <s> EDGE DENSITY <s> Abstract We show that if a graph G with n ≥ 3 vertices can be drawn in the plane such that each of its edges is involved in at most four crossings, then G has at most 6 n − 12 edges. This settles a conjecture of Pach, Radoicic, Tardos, and Toth, and yields a better bound for the famous Crossing Lemma: The crossing number, cr ( G ) , of a (not too sparse) graph G with n vertices and m edges is at least c m 3 n 2 , where c > 1 / 29 . This bound is known to be tight, apart from the constant c for which the previous best lower bound was 1/31.1. <s> BIB010 </s> A Survey on Graph Drawing Beyond Planarity <s> EDGE DENSITY <s> We prove that if an $n$-vertex graph $G$ can be drawn in the plane such that each pair of crossing edges is independent and there is a crossing-free edge that connects their endpoints, then $G$ has $O(n)$ edges. Graphs that admit such drawings are related to quasi-planar graphs and to maximal $1$-planar and fan-planar graphs. <s> BIB011 </s> A Survey on Graph Drawing Beyond Planarity <s> EDGE DENSITY <s> Abstract The notion of 1-planarity is among the most natural and most studied generalizations of graph planarity. A graph is 1-planar if it has an embedding where each edge is crossed by at most another edge. The study of 1-planar graphs dates back to more than fifty years ago and, recently, it has driven increasing attention in the areas of graph theory, graph algorithms, graph drawing, and computational geometry. This annotated bibliography aims to provide a guiding reference to researchers who want to have an overview of the large body of literature about 1-planar graphs. It reviews the current literature covering various research streams about 1-planarity, such as characterization and recognition, combinatorial properties, and geometric representations. As an additional contribution, we offer a list of open problems on 1-planar graphs. <s> BIB012 </s> A Survey on Graph Drawing Beyond Planarity <s> EDGE DENSITY <s> We introduce the family of k-gap-planar graphs for \(k \ge 0\), i.e., graphs that have a drawing in which each crossing is assigned to one of the two involved edges and each edge is assigned at most k of its crossings. This definition finds motivation in edge casing, as a \(k\)-gap-planar graph can be drawn crossing-free after introducing at most k local gaps per edge. We obtain results on the maximum density, drawability of complete graphs, complexity of the recognition problem, and relationships with other families of beyond-planar graphs. <s> BIB013
The problem of establishing the maximum number of edges in a given type of beyond-planar graph has been extensively studied in the literature. We recall some basic definitions needed to describe the main results in this research direction. Let F be a beyond-planar graph family and let G be an n-vertex graph in F . G is maximal (in F ) if adding any edge to G leads to a graph that is not in F . G is maximally dense if it has the maximum number of edges over all n-vertex graphs in F . The edge density of G is the ratio between its number of edges and its number of vertices. G is optimal if it has the maximum edge density over all graphs of F . Note that an optimal graph is also maximally dense, while the converse may not be true; similarly, a maximally dense graph is maximal, but there are maximal graphs that are not maximally dense; Figure 4 (a) shows a maximally dense 1-planar graph with 5 vertices that is not optimal; Figure 4 (b) shows a 1-planar graph with 12 vertices that is maximal but not optimal, and Figure 4 (c) shows an optimal 1-planar graph with 12 vertices. Density of k-planar graphs. For 1 ≤ k ≤ 4, Pach and Tóth prove that k-planar graphs have at most (k + 3)(n − 2) edges BIB001 , and they also use this result to improve an earlier lower bound on the crossing number of a graph. In particular, the resulting bounds are tight for k = 1 and for k = 2, which means that the optimal 1-planar graphs have 4n − 8 edges and the optimal 2-planar graphs have 5n − 10 edges. The best known upper bounds for k = 3 and k = 4 are 5.5n − 11 BIB006 and 6n − 12 BIB010 , respectively. For k > 4, the best known upper bound is 3, 81 √ k n BIB010 , which improves a previous bound of 4.108 √ k n BIB001 . Lower bounds on the edge density of maximal 1-planar graphs are given in Brandenburg et al. BIB007 . For bipartite 1-planar graphs, Karpov proves a tight bound of 3n − 6 when n is even and n 6, and of 3n − 9 otherwise  . Different subfamilies of 1-planar graphs have also been studied, such as 1-planar graphs where no two pairs of crossing edges share an end-vertex, called IC-planar graphs, and those for which two pairs of crossing edges share at  O (n log n) BIB005 straight-line (5-length-path)-sif O (n log n/ log log n) BIB005 straight-line (4-length-cycle)-sif O (n 8/5 ) BIB004 planarly-connected c n × BIB011 Most of the bounds in the table hold for simple drawings only; though few of them are still valid for nonsimple drawings. The symbol in column Tightness means that the bound is tight; the symbols × and + mean that the bound is tight up to a multiplicative or to an additive constant, respectively, while the symbol means that the bound may be far from tight. most one end-vertex, called NIC-planar graphs. We report these bounds in Table 2 . More results about the edge density of 1-planar graphs are surveyed in Kobourov et al. BIB012 . Density of k-quasi planar graphs. In 1996, Pach, Shahrokhi, and Szegedy conjectured that, for any fixed k ≥ 2, there exists a constant c k , depending only on k, such that every k-quasi planar graph on n vertices has at most c k n edges. This conjecture has been proved for k = 3 and k = 4 by various authors, with the best upper bounds currently known being 6.5n − 20  and 72(n − 2)  , respectively. For k > 4, the conjecture remains unproved, but several superlinear upper bounds have been established; the current best upper bound is c k n log n, for a suitable constant c k BIB008 . An O (n log n) upper bound for k-quasi planar graphs with x-monotone edges is also known BIB002 BIB003 . Density of fan-planar, k-fan-crossing-free, and k-gap graphs. Both fan-planar and 1-gap planar graphs on n vertices have at most 5n − 10 edges, which is a tight bound BIB013  . Recall that the same bound holds for 2-planar graphs. For k > 1, a k-gap planar graph has O ( √ kn) edges BIB013 . A fan-crossing-free graph has at most 4n − 8 edges, and at most 4n − 9 if the edges are drawn as straight lines BIB009 . These bounds are analogous to those for topological and geometric 1-planar graphs. For k > 2, k-fan-crossing-free graphs have at most 3(k − 1)(n − 2) edges BIB009 .