A crossing lemma for multigraphs
Let \(G\) be a drawing of a graph with \(n\) vertices and \(e > 4n\) edges, in which no two adjacent edges cross and any pair of independent edges cross at most once. According to the crossing lemma of \textit{M. Ajtai} et al. [Ann. Discrete Math. 12, 9--12 (1982; Zbl 0502.05021)] and \textit{F. T. Leighton} [Complexity issues in VLSI. Optimal layouts for the shuffle-exchange graph and other networks. Cambridge: MIT Press (1983)], the number of crossings in \(G\) is at least \(c\frac{e^3}{n^2}\), for a suitable constant \(c > 0\). \textit{L. A. Székely} [Comb. Probab. Comput. 6, No. 3, 353--358 (1997; Zbl 0882.52007)] generalized this result to multigraphs, establishing the lower bound \(c\frac{e^3}{mn^2}\), where \(m\) denotes the maximum multiplicity of an edge in \(G\). In this paper, the authors get rid of the dependence on \(m\) by showing that, as in the original crossing lemma, the number of crossings is at least \(c^\prime\frac{e^3}{n^2}\) for some \(c^\prime> 0\), provided that the ``lens (a region bounded by two parallel edges) enclosed by every pair of parallel edges in \(G\) contains at least one vertex. This settles a conjecture of Bekos, Kaufmann, and Raftopoulou.
- A crossing lemma for multigraphs
- A crossing lemma for the pair-crossing number
- A bipartite strengthening of the crossing Lemma
- A Bipartite Strengthening of the Crossing Lemma
- On the crossing number of some complete multipartite graphs
- An adjacency Lemma for critical multigraphs
- Crossing numbers of graphs
- The Crossing Number of Graphs: Theory and Computation
- On the crossing number of complete graphs
- On the crossing number of complete graphs
- A successful concept for measuring non-planarity of graphs: The crossing number.
- Applications of the crossing number
- Crossing Number is NP-Complete
- Crossing Numbers and Hard Erdős Problems in Discrete Geometry
- Crossing-Free Subgraphs
- Extremal problems in discrete geometry
- scientific article; zbMATH DE number 732977 (Why is no real title available?)
- scientific article; zbMATH DE number 1452728 (Why is no real title available?)
- scientific article; zbMATH DE number 1749054 (Why is no real title available?)
- Improved bounds for planar k-sets and related problems
- New bounds on crossing numbers
- Planar Separators
- The graph crossing number and its variants: a survey
- The number of crossings in multigraphs with no empty lens
- Making a graph crossing-critical by multiplying its edges
- On the number of edges of separated multigraphs
- On topological graphs with at most four crossings per edge
- Crossings between non-homotopic edges
- scientific article; zbMATH DE number 3914340 (Why is no real title available?)
- Quantitative restrictions on crossing patterns
- On the Maximum Number of Crossings in Star-Simple Drawings of K_n with No Empty Lens
- On the maximum number of crossings in star-simple drawings of \(K_n\) with no empty lens
- The number of crossings in multigraphs with no empty lens
- A crossing lemma for multigraphs
- Improving the crossing lemma by finding more crossings in sparse graphs
- A Bipartite Strengthening of the Crossing Lemma
- Edge-minimum saturated \(k\)-planar drawings
- Improving the crossing lemma by characterizing dense 2-planar and 3-planar graphs
- On the number of edges of separated multigraphs
- Improving the Crossing Lemma by characterizing dense 2-planar and 3-planar graphs
- Non-homotopic drawings of multigraphs
- A bipartite strengthening of the crossing Lemma
This page was built for publication: A crossing lemma for multigraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2189737)
