2022/08/25 by János Karl, Karl, János, Gézá Tóth +1 · 1 citation
Computer Science · Engineering · #Computational Geometry and Mesh Generation #Smart Parking Systems Research
paper · pdf · doi:10.48550/arxiv.2208.12140
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 4n-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 \em an odd number of times, then it is called 1-odd-planar and it has at most 5n-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.