0
$\begingroup$

Say that we draw a graph in the following way: we first draw $n$ planar embeddings of $K_{2,2}$ (that is, we first draw $n$ quadrilaterals) such there are no edges which cross. Then for each of the $K_ {2,2}$'s, we color 2 of its vertices red, 2 of its vertices blue, such that no edge connects vertices of the same color. Finally, for every planar embedding of $K_{2,2}$, for all of its red vertices, we draw an edge to every single blue vertex in our drawing.

I am trying to prove that if $c$ is the smallest amount of crossings out of any drawing which is produced by the above schema, that there exists a drawing with $c$ crossings where all of the planar embeddings of $K_{2,2}$ were drawn "inside" each other- that is, for any 2 planar embeddings of $K_{2,2}$, one of these embeddings completely encircles another.

For context, I am studying the properties of bipartite graph drawings, and have thought of this question myself as it could be of use in my research, and the statement I am trying to prove seemed intuitively plausible. I would be highly appreciative of any help towards showing either the truth or falsehood of the provided statement.

Improve this question
$\endgroup$
3
  • $\begingroup$ I think with two of these $4$-cycles, the minimum number of edge-crossings is four, and that can be achieved without one $4$-cycle being inside the other one. $\endgroup$
    – Gerry Myerson
    Commented Jul 19 at 6:12
  • 1
    $\begingroup$ @GerryMyerson you are correct; I actually meant to ask a slightly different claim, which was whether the minimum number of crossings can be realized with the cycles inside of each other. I have edited the question. $\endgroup$
    – Avi
    Commented Jul 19 at 16:58
  • $\begingroup$ If I understood well, you're practically asking Zarankiewicz's conjecture: mathworld.wolfram.com/ZarankiewiczsConjecture.html $\endgroup$
    – domotorp
    Commented Jul 19 at 20:51

0

Reset to default

You must log in to answer this question.