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?

$\endgroup$
4
  • 5
    $\begingroup$ Should the title be "Not quite planar graphs"? $\endgroup$ 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
    Sep 19, 2022 at 14:32
  • $\begingroup$ Made my comment into an answer below with some more info. $\endgroup$
    – Tony Huynh
    Sep 19, 2022 at 14:40
  • $\begingroup$ @SamHopkins Thanks, I edited the title to a better (I think/hope) title. $\endgroup$ Sep 21, 2022 at 7:10

1 Answer 1

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.