Details

Autor(en) / Beteiligte

• Ábrego, Bernardo M.
• Fernández-Merchant, Silvia
• Figueroa, Ana Paulina
• Montellano-Ballesteros, Juan José
• Rivera-Campo, Eduardo

Titel

The Crossing Number of Twisted Graphs

Ist Teil von

• Graphs and combinatorics, 2022-10, Vol.38 (5), Article 134

Ort / Verlag

Tokyo: Springer Japan

Erscheinungsjahr

2022

Quelle

SpringerLINK Journals

Beschreibungen/Notizen

• We consider twisted graphs , that is, topological graphs that are weakly isomorphic to subgraphs of the complete twisted graph T n . We 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 1/6. Let e k ( n ) be the maximum number of edges over all twisted graphs with n vertices and local crossing number at most k . We give lower and upper bounds for e k ( n ) and settle its exact value for k ∈ { 0 , 1 , 2 , 3 , 6 , 10 } . We conjecture that for every t ≥ 1 , e ( t 2 ) ( n ) = ( t + 1 ) n - t + 2 2 , n ≥ t + 1 .