A Crossing Lemma for Multigraphs
- PDF / 618,221 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 45 Downloads / 195 Views
A Crossing Lemma for Multigraphs János Pach1 · Géza Tóth2,3 Received: 25 June 2018 / Revised: 23 November 2018 / Accepted: 4 December 2018 © Springer Science+Business Media, LLC, part of Springer Nature 2018
Abstract 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 celebrated Crossing Lemma of Ajtai, Chvátal, Newborn, Szemerédi and Leighton, 3 the number of crossings in G is at least c ne 2 , for a suitable constant c > 0. In a seminal paper, Székely generalized this result to multigraphs, establishing the lower bound e3 c mn 2 , where m denotes the maximum multiplicity of an edge in G. We get rid of the dependence on m by showing that, as in the original Crossing Lemma, the number of 3 crossings is at least c ne 2 for some c > 0, provided that the “lens” enclosed by every pair of parallel edges in G contains at least one vertex. This settles a conjecture of Bekos, Kaufmann, and Raftopoulou. Keywords Crossing number · Crossing Lemma · Separator theorem · Bisection width Mathematics Subject Classification 05C10
1 Introduction A drawing of a graph G is a representation of G in the plane such that the vertices are represented by points, the edges are represented by simple continuous arcs connecting the corresponding pair of points without passing through any other point representing
Editor in Charge: Kenneth Clarkson János Pach [email protected]; [email protected] Géza Tóth [email protected] 1
Ecole Polytechnique Fédérale de Lausanne and Rényi Institute, Hungarian Academy of Sciences, P.O.Box 127, Budapest 1364, Hungary
2
Rényi Institute, Hungarian Academy of Sciences, P.O.Box 127, Budapest 1364, Hungary
3
Department of Mathematical Analysis, Budapest University of Technology and Economics, Budapest 1111, Hungary
123
Discrete & Computational Geometry
a vertex. In notation and terminology we do not make any distinction between a vertex (edge) and the point (resp., arc) representing it. Throughout this note we assume that any pair of edges intersect in finitely many points and no three edges pass through the same point. A common interior point of two edges at which the first edge passes from one side of the second edge to the other, is called a crossing. A very “successful concept for measuring non-planarity” of graphs is the crossing number of G [15], which is defined as the minimum number cr(G) of crossing points in any drawing of G in the plane. For many interesting variants of the crossing number, see [11,12]. Computing cr(G) is an NP-complete problem [4]. The following statement, proved independently by Ajtai et al. [1] and Leighton [7], gives a lower bound on the crossing number of a graph in terms of its number of vertices and number of edges. Crossing Lemma [1,7] For any graph G with n vertices and e > 4n edges, we have cr(G) ≥
1 e3 . 64 n 2
Apart from the exact value of the constant, the order of magnitude of this bound cannot be improved. This lemma has many important applications,
Data Loading...
