A Survey on Graph Drawing Beyond Planarity <s> Density of other graph families. <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> BIB001 </s> A Survey on Graph Drawing Beyond Planarity <s> Density of other graph families. <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> BIB002 </s> A Survey on Graph Drawing Beyond Planarity <s> Density of other graph families. <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> BIB003 </s> A Survey on Graph Drawing Beyond Planarity <s> Density of other graph families. <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> BIB004 </s> A Survey on Graph Drawing Beyond Planarity <s> Density of other graph families. <s> Let G be a topological graph with n vertices, i.e., a graph drawn in the plane with edges drawn as simple Jordan curves. It is shown that, for any constants k,l, there exists another constant C(k,l), such that if G has at least C(k,l)n edges, then it contains a k×l-gridlike configuration, that is, it contains k+l edges such that each of the first k edges crosses each of the last l edges. Moreover, one can require the first k edges to be incident to the same vertex. <s> BIB005 </s> A Survey on Graph Drawing Beyond Planarity <s> Density of other graph families. <s> Keywords: crossing number ; bisection width of a graph Note: Professor Pach's number: [105]. Also in: Proc. 10th ACM Symposium on Computational Geometry, 1994, 198-202. Reference DCG-ARTICLE-1996-001 Record created on 2008-11-14, modified on 2017-05-12 <s> BIB006 </s> A Survey on Graph Drawing Beyond Planarity <s> Density of other graph families. <s> A graph drawn in the plane is called k-quasi-planar if it does not contain k pair- wise crossing edges. It has been conjectured for a long time that for every fixed k ,t he maximum number of edges of a k-quasi-planar graph with n vertices is O(n). The best known upper bound is n(log n) O(log k) . In the present paper, we improve this bound to (nlog n)2 α(n) ck in the special case where the graph is drawn in such a way that every pair of edges meet at most once. Here α(n) denotes the (extremely slowly growing) inverse of the Ackermann function. We also make further progress on the conjecture for k-quasi-planar graphs in which every edge is drawn as an x-monotone curve. Extending some ideas of Valtr, we prove that the maximum number of edges of such graphs is at most 2 ck 6 nlog n. <s> BIB007 </s> A Survey on Graph Drawing Beyond Planarity <s> Density of other graph families. <s> A simple undirected graph G = (V, E) is k-planar if it can be drawn in the plane such that each edge is crossed at most k times, incident edges do not cross, and a pair of edges must not cross twice. Such graphs have attracted many graph drawers, see [1] and the references given there. <s> BIB008 </s> A Survey on Graph Drawing Beyond Planarity <s> Density of other graph families. <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> BIB009 </s> A Survey on Graph Drawing Beyond Planarity <s> Density of other graph families. <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> BIB010 </s> A Survey on Graph Drawing Beyond Planarity <s> Density of other graph families. <s> A topological graph G is a graph drawn in the plane with vertices represented by points and edges represented by continuous arcs connecting the vertices. If every edge is drawn as a straight-line segment, then G is called a geometric graph. A k-grid in a topological graph is a pair of subsets of the edge set, each of size k, such that every edge in one subset crosses every edge in the other subset. It is known that every n-vertex topological graph with no k-grid has O-k(n) edges. We conjecture that the number of edges of every n-vertex topological graph with no k-grid such that all of its 2k edges have distinct endpoints is 0 k(n). This conjecture is shown to be true apart from an iterated logarithmic factor log* n. A k-grid is natural if its edges have distinct endpoints, and the arcs representing each of its edge subsets are pairwise disjoint. We also conjecture that every n-vertex geometric graph with no natural k-grid has Ok(n) edges, but we can establish only an O-k(n log(2) n) upper bound. We verify the above conjectures in several special cases. (C) 2014 Elsevier B.V. All rights reserved. <s> BIB011 </s> A Survey on Graph Drawing Beyond Planarity <s> Density of other graph families. <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> BIB012 </s> A Survey on Graph Drawing Beyond Planarity <s> Density of other graph families. <s> A k-planar graph is a graph that can be drawn in the plane such that every edge is crossed at most k times. For \(k \le 4\), Pach and Toth [20] proved a bound of \((k+3)(n-2)\) on the total number of edges of a k-planar graph, which is tight for \(k=1,2\). For \(k=3\), the bound of \(6n-12\) has been improved to \(\frac{11}{2}n-11\) in [19] and has been shown to be optimal up to an additive constant for simple graphs. In this paper, we prove that the bound of \(\frac{11}{2}n-11\) edges also holds for non-simple 3-planar graphs that admit drawings in which non-homotopic parallel edges and self-loops are allowed. Based on this result, a characterization of optimal 3-planar graphs (that is, 3-planar graphs with n vertices and exactly \(\frac{11}{2}n-11\) edges) might be possible, as to the best of our knowledge the densest known simple 3-planar is not known to be optimal. <s> BIB013 </s> A Survey on Graph Drawing Beyond Planarity <s> Density of other graph families. <s> A graph is $k$-planar if it can be drawn in the plane such that no edge is crossed more than $k$ times. While for $k=1$, optimal $1$-planar graphs, i.e., those with $n$ vertices and exactly $4n-8$ edges, have been completely characterized, this has not been the case for $k \geq 2$. For $k=2,3$ and $4$, upper bounds on the edge density have been developed for the case of simple graphs by Pach and Toth, Pach et al. and Ackerman, which have been used to improve the well-known "Crossing Lemma". Recently, we proved that these bounds also apply to non-simple $2$- and $3$-planar graphs without homotopic parallel edges and self-loops. ::: In this paper, we completely characterize optimal $2$- and $3$-planar graphs, i.e., those that achieve the aforementioned upper bounds. We prove that they have a remarkably simple regular structure, although they might be non-simple. The new characterization allows us to develop notable insights concerning new inclusion relationships with other graph classes. <s> BIB014
Since a skewness-k graph G becomes planar after the removal of at most k edges, G has at most 3n − 6 + k edges. This bound is trivially achieved by adding k edges to a maximal planar graph. Similarly, removing at most k vertices from an n-vertex kapex graph yields a planar graph, and thus k-apex graphs have at most 3(n − k ) − 6 + k i=1 (n − i) edges. A graph attaining this bound is constructed from a maximal planar graph, iteratively adding one vertex connected to all other vertices of the graph. (k, l )-grid-free and radial-(k, l )-grid-free graphs have at most c k,l n edges (where c k,l is constant in n but depends on k and l) and 8 · 24 l kn edges, respectively BIB005 , while natural-k-grid-free graphs have O (n log 4k−6 n) edges BIB011 . Concerning straight-line (3-length-path)-sif and straight-line (4-length-path)-sif graphs, it is shown that they have O (n log n) and O (n log n/ log log n) edges, respectively BIB004 , while straight-line (4-length-cycle)-sif graphs have O (n 8/5 ) edges BIB003 . Finally, planarly connected graphs have c n edges, where c is a constant BIB012 . Table 2 summarizes the discussed bounds on the edge density of beyond-planar graphs. Open problems. Although Turán-type questions on beyond-planar drawings have been studied for a long time and the geometric graph theory literature contains many results, there are still beautiful open problems. For several families of beyond-planar graphs, the upper bounds on the maximum number of edges reported in Table 2 are not tight. Hence, the goal of achieving tight bounds for each of these families gives rise to an array of challenging problems. We find particular interest in the following (see also   ). Problem 1. Find a tight upper bound on the edge density of k-quasi planar graphs for k > 4. The problem is relevant also when the edges are drawn as x-monotone curves. Problem 2. Find tight upper bounds on the edge density of (simple) k-planar graphs for k ≥ 3. Starting references for Problem 1 are listed in the References BIB007 BIB010 BIB001 BIB002 . We recall that Pach et al. conjecture an upper bound that is linear in the number of vertices BIB006 . Concerning Problem 2, recent papers discuss the edge density of (not necessarily simple) 3-planar graphs BIB013 BIB014 . Another research direction is concerned with providing lower bounds on the number of edges of maximal beyond-planar graphs. This type of question is mostly unexplored; results are known for 1-and 2-planar graphs BIB008 BIB009 . We suggest the following.