# A weak version of planarity

A planar graph is such that one can draw it on the plane so that edges do not intersect except at vertices. Consider a weaker condition:

• We can draw the graph on a plane so that for every two edges that intersect properly (that is, not at a vertex of the graph) there are no edges that intersect properly both these edges.

What is known about such graphs?

Edit: What if we strengthen the condition (similar to outplanarity):

• We can draw the graph on a plane so that all vertices belong to a circle and for every two edges that intersect properly (that is, not at a vertex of the graph) there are no edges that intersect properly both these edges.
• Robertson-Seymour...? Oct 14, 2016 at 4:18
• Do you have an example of a graph lacking this property? Oct 14, 2016 at 4:24
• If I understand correctly and you still demand that no edge passes through a vertex that is not an endpoint of an edge, then these graphs are called quasi-planar graphs. It is known, for instance, that they have a linear number of edges (Agarwal, P.K., Aronov, B., Pach, J. et al. Combinatorica (1997) 17: 1. doi:10.1007/BF01196127) Edit: It seems they also require that any two edges meet in at most one point. Oct 14, 2016 at 8:51
• I can't edit again, so another comment seems to be necessary: The mentioned extra condition was removed by Pach, Radoicic and Toth in "Relaxing planarity for topological graphs" (sorry for missing accents), thus proving the linear bound. Oct 14, 2016 at 8:59
• @monkeymaths: Thank you! It is exactly what I needed. If you make it into an answer, I will accept it.
– user6976
Oct 14, 2016 at 12:28

A graph drawn in the plane (with edges represented by curves that do not pass through vertices except for their endpoints) is called $k$-quasi-planar if there are is no set of $k$ pairwise intersecting curves. For $k=3$ they are usually just called quasi-planar.
Building on earlier work by Agarwal et al (doi:10.1007/BF01196127), Pach, Radoicic and Toth showed in "Relaxing planarity for topological graphs" that there is a constant $C$ such that every quasi-planar graph on $n$ vertices has at most $Cn$ edges (Theorem 7.1).