Crossing lemma for the odd-crossing number

Karl, Janos and Tóth, Géza (2023) Crossing lemma for the odd-crossing number. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 108. ISSN 0925-7721

Preview

Text 1-s2.0-S092577212200044X-main.pdf Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (269kB) | Preview

Abstract

A graph is 1-planar, if it can be drawn in the plane such that there is at most one crossing on every edge. It is known, that 1-planar graphs have at most 4 pi - 8 edges. We prove the following odd-even generalization. If a graph can be drawn in the plane such that every edge is crossed by at most one other edge an odd number of times, then it is called 1-odd-planar and it has at most 5 pi - 9 edges. As a consequence, we improve the constant in the Crossing Lemma for the odd-crossing number, if adjacent edges cross an even number of times. We also give upper bound for the number of edges of k-odd-planar graphs.(C) 2022 The Author(s). Published by Elsevier B.V.

Actions (login required)

Edit Item