The crossing number of twisted graphs (Q2163801): Difference between revisions

The complete twisted graph \(T_n\) is a complete simple topological graph with vertices \(v_1, v_2, \dots, v_n\) such that two edges \(v_iv_j\) and \(v_pv_q\) cross if and only if \(i<p<q<j\) or \(p<i<j<q\). A simple topological graph \(G\) is a twisted graph if \(G\) is weakly isomorphic to a simple topological subgraph of \(T_n\). In this paper, the authors determine the exact minimum number of crossings of edges among the set of twisted graphs with \(n\) vertices and \(m\) edges, state a version of the crossing lemma for twisted graphs, and conclude that the mid-range crossing constant for twisted graphs is \(\frac 1 6\). Let \(e_k(n)\) denote the maximum number of edges over all twisted graphs with \(n\) vertices and local crossing number at most \(k\). They give lower and upper bounds for \(e_k(n)\) and settle its exact value for \(k\in \{0, 1, 2, 3, 6, 10\}\), and pose a conjecture on \(e_k(n)\) for \(k=\) \(\binom{t}{2}\) and \(t\geq 1.\)