4
$\begingroup$

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.
Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Robertson-Seymour...? $\endgroup$
    – Charles
    Commented Oct 14, 2016 at 4:18
  • 1
    $\begingroup$ Do you have an example of a graph lacking this property? $\endgroup$
    – Gerry Myerson
    Commented Oct 14, 2016 at 4:24
  • 7
    $\begingroup$ 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. $\endgroup$
    – monkeymaths
    Commented Oct 14, 2016 at 8:51
  • 6
    $\begingroup$ 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. $\endgroup$
    – monkeymaths
    Commented Oct 14, 2016 at 8:59
  • 3
    $\begingroup$ @monkeymaths: Thank you! It is exactly what I needed. If you make it into an answer, I will accept it. $\endgroup$
    – user6976
    Commented Oct 14, 2016 at 12:28

1 Answer 1

Reset to default
3
$\begingroup$

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).

Improve this answer
$\endgroup$

You must log in to answer this question.