3
$\begingroup$

A graph is planar if it can be drawn on the plane in such a way that its edges do not cross each other.

A graph is $k$-planar if it can be drawn on the plane in such a way that each of its edges is crossed at most $k$ times.

There is also a concept of almost planar graphs that relies on edge deletions or contractions.

I am dealing with another kind of graphs: they can be drawn in the plane in such a way that at most $k$ pairs of edges intersect.

Is there a terminology for such graphs?

Improve this question
$\endgroup$
4
  • 5
    $\begingroup$ Should the title be "Not quite planar graphs"? $\endgroup$
    – Sam Hopkins
    Commented Sep 19, 2022 at 14:18
  • 2
    $\begingroup$ These are the graphs with pairwise crossing number at most $k$. See en.wikipedia.org/wiki/…. $\endgroup$
    – Tony Huynh
    Commented Sep 19, 2022 at 14:32
  • $\begingroup$ Made my comment into an answer below with some more info. $\endgroup$
    – Tony Huynh
    Commented Sep 19, 2022 at 14:40
  • $\begingroup$ @SamHopkins Thanks, I edited the title to a better (I think/hope) title. $\endgroup$
    – Matthieu Latapy
    Commented Sep 21, 2022 at 7:10

1 Answer 1

Reset to default
5
$\begingroup$

These are the graphs with pairwise crossing number or pair-crossing number at most $k$. Note that it is an open problem whether the pair-crossing number is actually equal to the usual crossing number of a graph. See Crossing number, pair-crossing number, and expansion and The Graph Crossing Number and its Variants: A Survey for more info.

Improve this answer
$\endgroup$
2
  • $\begingroup$ There is also Marcus Schaefer's dynamic survey updated most recently in April this year: link $\endgroup$
    – Brendan McKay
    Commented Sep 20, 2022 at 2:07
  • $\begingroup$ Thanks Brendan! I added the reference. $\endgroup$
    – Tony Huynh
    Commented Sep 20, 2022 at 12:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .