12
$\begingroup$

Suppose we have a graph G. Is it true that we can map its vertices to the plane such that when connecting neighboring vertices with segments, then any induced cycle of G that has length at least 4 will have two edges that intersect?

What if I want each induced cycle of length at least 4 to be in a non-convex position? (If we write a bigger number instead of 4, then this would be some kind of strengthening of the theorem of Erdos-Szekeres.)

What if I want k induced cycles that do not intersect (any other or themselves)?

I suspect that the answer to all these questions is negative, i.e. there is a graph that we cannot linearly map with ruining all its induced cycles. I would also be very interested in any related results.

*Update March 19. I realized that I can show that there is a dense graph whose embedding will have an induced $C_4$ in convex position (whose edges might intersect). For a proof sketch, see my answer.

*Update April 3. Now I realized that if the graph is sparse in the sense that its degeneracy is constant, then its chromatic number is also constant, in which case we can put the vertices that belong to the same color class close to each other, which would mean that it is not possible to have too many disjoint cycles. So a graph with a linear number of edges has a drawing with at most a constant number of disjoint cycles.

*Remaining Question. Is there a method that guarantees non-crossing cycle(s) and does not use a counting argument but rather some topology?

Improve this question
$\endgroup$
3
  • $\begingroup$ I don't follow the details of your argument, but $\log \left( n^{log n} \right)$ is $(\log n)^2$, not $n \log n$. This seems to indicate an error in the sentence beginning "Firstly". I'm afraid that I am lost enough that I can't figure out whether this is important or just a minor typo. $\endgroup$
    – David E Speyer
    Mar 19, 2011 at 11:30
  • $\begingroup$ Dear Domotorp, it is a little hard to understand your updates and what is known and what is still not regarding your initial question. Perhaps add an answer with a description of what is known? $\endgroup$
    – Gil Kalai
    Apr 8, 2011 at 10:29
  • $\begingroup$ I edited my question a bit, I hope this highlights the remaining question. $\endgroup$
    – domotorp
    Apr 9, 2011 at 20:11

3 Answers 3

Reset to default
2
$\begingroup$

Just a comment. If there is an embedding of $G$ as a straight-line thrackle, then every pair of non-incident edges cross, and so all induced cycles (of length $\ge 4$) intersect. Conway's thrackle conjecture—that every thrackle satisfies $E \le V$—has long been known to hold for straight-line thrackles. So you might gain some insight by examining the literature on thrackles; see this webpage or this problem summary. In particular, the 4-cycles play a special role, as they are the only cycles that are not thrackles.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for your answer. I think the thrackle problem is quite different, as there the requirement is very restricting that they have to cross exactly once, which enable to use e.g. parity arguments which would not work for this problem. I imagine this to be more similar to some Borsuk-Ulam type arguments, or theorems about simplices sharing many points, e.g. arxiv.org/abs/1005.1392 $\endgroup$
    – domotorp
    Mar 18, 2011 at 7:12
1
$\begingroup$

A counting argument proves that there is a (dense) graph whose embeddings always have a $C_4$ in convex position (with possibly intersecting edges). I am sure that a more careful counting would also prove several copies of convex $C_4$'s without intersecting edges.

The proof is a counting argument, we can describe every graph that has an embedding without a convex, induced $C_4$ with less than $n^2/2$ bits. Firstly, there are $n^{O(n)}$ order types (which describe the position of the vertices in the embedding), so encoding an order type requires $n\log n$ bits (we don't care about the constants). Divide the vertices into $n$ groups of size $\sqrt n$ such that every edge is in at most one group (this is possible, again we might lose some constants). In each group, there are $k=\log n$ vertices in convex position. So we know that there cannot be an induced $C_4$ among them. There are only $2^{k^2/4}$ such graphs. So the edges can be described with $k^2/4$ bits instead of the usual $k^2/2$, this means that in each group we spare $k^2/4$ bits. Thus in total we win $nk^2/4$, which is about $n\log^2 n\ge n\log n$, we are done. Note that this proof works for any graph instead of the $C_4$.

Improve this answer
$\endgroup$
0
$\begingroup$

It will be hard to do with complete graphs or near complete. Bipartite graphs come close; perhaps you could try some characterization involving near-bipartite graphs.

Of course, you can artificially force the condition by drawing a curve for each edge, and requesting that all curves meet at a (nonvertex) point in the plane.

Gerhard" Ask Me About System Design" Paseman, 2011.03.17

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ for bipartite graphs everything is ok: you may draw points of one part along one line, and of other part along some parallel line $\endgroup$
    – Fedor Petrov
    Mar 17, 2011 at 10:55
  • 2
    $\begingroup$ He only asks for induced cycles. For the complete graph, the only induced cycles are triangles, so it is trivially doable. The thing which I find challenging about this problem is that adding edges can both make it harder (by creating more cycles) or easier (by making some cycles non-induced.) $\endgroup$
    – David E Speyer
    Mar 17, 2011 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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