Search

We investigate the total number of edge crossings (i.e., the crossing number) of the Euclidean minimum weight Laman graph \(\mathsf {MLG}(P)\) on a planar point set P. Bereg et al. (2016) showed that the upper and lower bounds for the crossing number of \(\mathsf {MLG}(P)\) are \(6|P|-9\) and \(|P|-3\), respectively. In this paper, we improve these upper and lower bounds given by Bereg et al. (2016) to \(2.5|P|-5\) and \((1.25-\varepsilon )|P|\) for any \(\varepsilon > 0\), respectively. Especially, for improving the upper bound, we introduce a novel counting scheme based on some geometric observations.

The crossing number of a graph G, denoted by cr(G), is defined as the smallest possible number of edge-crossings in a drawing of G in the plane. The cone CG, obtained from G by adding a new vertex adjacent to all the vertices in G. Let $$\phi _\mathrm {s}(k)=\min \{cr(CG)-cr(G)\}$$ , where the minimum is taken over all the simple graphs G with crossing number k. Alfaro et al. (SIAM J Discrete Math, 32: 2080–2093, 2018) determined $$\phi _\mathrm {s}(k)\le k$$ for $$k\ge 3$$ , and proved $$\phi _\mathrm {s}(3)=3$$ , $$\phi _\mathrm {s}(4)=4$$ and $$\phi _\mathrm {s}(5)=5$$ . In this work, we improve the upper bound for $$\phi _\mathrm {s}(k)$$ and our main result includes the following, slightly surprising, fact: $$\phi _\mathrm {s}(6)=5$$ and $$\phi _\mathrm {s}(7)=6$$ .

A 1-planar graph is a graph which has a drawing on the plane such that each edge has at most one crossing. Czap and Hudak showed that every 1-planar graph with n vertices has crossing number at most $$n-2$$ . In this paper, we prove that every maximal 1-planar graph G with n vertices has crossing number at most $$n-2-(2\lambda _1+2\lambda _2+\lambda _3)/6$$ , where $$\lambda _1$$ and $$\lambda _2$$ are respectively the numbers of 2-degree and 4-degree vertices in G, and $$\lambda _3$$ is the number of odd vertices w in G such that either $$d_G(w)\le 9$$ or $$G-w$$ is 2-connected. Furthermore, we show that every 3-connected maximal 1-planar graph with n vertices and m edges has crossing number $$m-3n+6$$ .

Zarankiewicz’s conjecture states that the crossing number $$\text {cr}(K_{m,n})$$ of the complete bipartite graph $$K_{m,n}$$ is $$Z(m,n):=\lfloor \frac{m}{2}\rfloor \lfloor \frac{m-1}{2}\rfloor \lfloor \frac{n}{2}\rfloor \lfloor \frac{n-1}{2}\rfloor$$ , where $$\lfloor x \rfloor$$ denotes the largest integer no more than x. It is conjectured that the crossing number $$\text {cr}(K_{1,m,n})$$ of the complete tripartite graph $$K_{1,m,n}$$ is $$Z(m+1,n+1)-\lfloor \frac{m}{2}\rfloor \lfloor \frac{n}{2}\rfloor$$ . When one of m and n is even, Ho proved that this conjecture is true if Zarankiewicz’s conjecture holds, in 2008. When both m and n are odd, Ho proved that $$\text {cr}(K_{1,m,n})\ge \text {cr}(K_{m+1,n+1})-\left\lfloor \frac{n}{m}\lfloor \frac{m}{2}\rfloor \lfloor \frac{m+1}{2}\rfloor \right\rfloor$$ and conjectured that equality holds in this inequality. Which one of the conjectures may be true? In this paper, we proved that if Zarankiewicz’s conjecture holds, then the former one is true.

In this paper, we establish the crossing number of join product of 5-wheel with n isolated vertices. In addition, the exact values for the crossing numbers of Cartesian products of the wheels of order at most five with any tree T are given.

The 1-crossing index of a graph G is the smallest integer k such that the k th iterated line graph of G has crossing number greater than 1. In this paper, we show that the 1-crossing index of a graph is either infinite or it is at most 5. Moreover, we give a full characterization of all graphs with respect to their 1-crossing index.

The crossing number of a graph G is the minimum number of edge crossings over all drawings of G in the plane. A graph G is k-crossing-critical if its crossing number is at least k, but if we remove any edge of G, its crossing number drops below k. There are examples of k-crossing-critical graphs that do not have drawings with exactly k crossings. Richter and Thomassen proved in 1993 that if G is k-crossing-critical, then its crossing number is at most $$2.5\, k+16$$ 2.5 k + 16 . We improve this bound to $$2k+8\sqrt{k}+47$$ 2 k + 8 k + 47 .

The main aim of the paper is to give the crossing number of join product G+Dn for the disconnected graph G of order five consisting of the complete graph K4 and of one isolated vertex. In the proofs, it will be extend the idea of the minimum numbers of crossings between two different subgraphs from the set of subgraphs which do not cross the edges of the graph G onto the set of subgraphs which cross the edges of the graph G exactly one times. All methods used in the paper are new, and they are based on combinatorial properties of cyclic permutations. Finally, by adding some edges to the graph G, we are able to obtain the crossing numbers of the join product with the discrete graph Dn for two new graphs.

The crossing number of a graph G, Cr(G) is the minimum number of edge crossings overall good drawings of G. Among the well-known four standard graph products namely Cartesian product, Kronecker product, strong product and lexicographic product, the one that is most difficult to deal with is the Kronecker product. P.K. Jha and S. Devishetty have analyzed the upper bounds for crossing number of Kronecker product of two cycles in, “Orthogonal Drawings and the Crossing Numbers of the Kronecker product of two cycles”, J. Parallel Distrib. Comput. 72 (2012), 195–204. For any graph G except and K4 of order at most four, the graph is planar. In this paper, we establish the crossing number of Kronecker product of a complete tripartite graph with path and as a corollary, we show that its rectilinear crossing number is same as its crossing number. Also, we give the open problems on the crossing number of above mentioned graphs.

Nowadays, the fingerprint scanner widely used to records attendance. However, this technology has a weakness. Much research has done to improve the attendance system by utilizing mobile technology, like usage a fingerprint smartphone and location by GPS sensor to validate user location manually. In this research, we developed an application to enhance the records attendance system with a smartphone by crossing numbers to verify user position automatically, which implemented in a mobile app. This application using the PNPOLY method for detecting the location of the user inside of the polygon area predetermined. This method is part of the crossing number algorithm for increasing x and fixed y from point P, which x is latitude, and y is a longitude. The result of the experiment demonstrated that the percentage of successful validate user coordinate inside edges of the polygon boundary is 87%, depending on the GPS sensor embedded into a mobile device.

This is the final draft, after peer-review, of a manuscript published in Journal of Graph Theory. The published version is available online at https://doi.org/10.1002/jgt.22613

Computing the crossing number of a graph is NP-hard. In the paper, for a disconnected 6-vertex graph $$Q =C_{5}\cup K_{1}$$ , we obtain the crossing number $$Z(6,n)+\lfloor \frac{n}{2}\rfloor $$ of the graph $$Q_{n}$$ which is the join product of Q with the discrete graph by introducing the “rotation” method. Moreover, we give crossing numbers for join products of Q with the path and the cycle. Besides, we also get directly crossing numbers for join products of some connected 6-vertex graphs with the path and the cycle, some of which were studied by M. Klesc, D. Kravecova, and J. Petrillova.

We give the crossing number of the join product$W_{4}+D_{n}$, where$W_{4}$is the wheel on five vertices and$D_{n}$consists of$n$isolated vertices. The proof is based on calculating the minimum number of crossings between two different subgraphs from the set of subgraphs which do not cross the edges of the graph$W_{4}$and from the set of subgraphs which cross the edges of$W_{4}$exactly once.

In this paper, prime coloring and its chromatic number of some crossing number zero graphs are depicted and its results are vali-dated with few theorems. Prime Coloring is defined as G be a loop less and Without multiple edges with n distinct Vertices on Color class C={c1,c2,c3,…..cn} a bijection ψ:V {c1,c2,c3,…..cn} if for each edge e = cicj ,i≠j , gcd{ ψ (ci), ψ (cj)}=1, ψ (ci) and ψ (cj) receive distinct Colors. The Chromatic number of Prime coloring is minimum cardinality taken by all the Prime colors. It is denoted by η (G).

A bipartite-cylindrical drawing of the complete bipartite graph $$ K_{m,n} $$ is a drawing on the surface of a cylinder, where the vertices are placed on the boundaries of the cylinder, one vertex-partition per boundary, and the edges do not cross the boundaries. The bipartite-cylindrical crossing number of $$ K_{m,n}$$, denoted by $$ cr_\circledcirc (K_{m,n}) $$, is the minimum number of crossings among all bipartite-cylindrical drawings of $$ K_{m,n} $$. This problem is equivalent to minimizing the number of crossings in drawings of $$ K_{m,n} $$ in the plane where each of the vertex classes in the bipartition is placed on a circle and the edges do not cross the two circles. We determine $$ cr_\circledcirc (K_{m,n}) $$ and give explicit constructions that achieve this number. This in turn gives an alternative proof to the Harary–Hill Conjecture restricted to a subclass of cylindrical drawings of the complete graph.

We consider the problem of determining the 2-page book crossing number of the complete graph $$ K_n $$ when the number of edges in each page is given. We find upper and lower bounds of the right order of magnitude depending on the number of edges in the page with the least number of edges.

In [C. Thomassen, Tilings of the torus and the Klein bottle and vertex-transitive graphs on a fixed surface, Trans. Amer. Math. Soc. 323 (1991) 605–635], Thomassen described completely all (except finitely many) regular tilings of the torus S1 and the Klein bottle N2 into (3,6)-tilings, (4,4)-tilings and (6,3)-tilings. Many authors made great efforts to investigate the crossing number (in the plane) of the Cartesian product of an m-cycle and an n-cycle, which is a special (4,4)-tiling. For other tilings, there are quite rare results concerning on their crossing numbers. This motivates us in the paper to determine the crossing number of a hexagonal graph H3, n, which is a special kind of (3,6)-tilings.

Given a fixed positive integer k , the k -planar local crossing number of a graph G , denoted by LCR k ( G ) , is the minimum positive integer L such that G can be decomposed into k subgraphs, each of which can be drawn in a plane such that no edge is crossed more than L times. In this note, we show that under certain natural restrictions, the ratio LCR k ( G ) ∕ LCR 1 ( G ) is of order 1 ∕ k 2 , which is analogous to the result of Pach et al. (2018) for the k -planar crossing number CR k ( G ) (defined as the minimum positive integer C for which there is a k -planar drawing of G with C total edge crossings). As a corollary of our proof we show that, under similar restrictions, one may obtain a k -planar drawing of G with both the total number of edge crossings as well as the maximum number of times any edge is crossed essentially matching the best known bounds. Our proof relies on the crossing number inequality and several probabilistic tools such as concentration of measure and the Lovasz local lemma.

Systematic enumeration and identification of unique 3D spatial topologies of complex engineering systems such as automotive cooling layouts, hybrid-electric power trains, and aero-engines are essential to search their exhaustive design spaces to identify spatial topologies that can satisfy challenging system requirements. However, efficient navigation through discrete 3D spatial topology options is a very challenging problem due to its combinatorial nature and can quickly exceed human cognitive abilities at even moderate complexity levels. Here we present a new, efficient, and generic design framework that utilizes mathematical spatial graph theory to represent, enumerate, and identify distinctive 3D topological classes for an abstract engineering system, given its system architecture (SA) — its components and interconnections. Spatial graph diagrams (SGDs) are generated for a given SA from zero to a specified maximum crossing number. Corresponding Yamada polynomials for all the planar SGDs are then generated. SGDs are categorized into topological classes, each of which shares a unique Yamada polynomial. Finally, for each topological class, one 3D geometric model is generated for an SGD with the fewest interconnect crossings. Several case studies are shown to illustrate the different features of our proposed framework. Design guidelines are also provided for practicing engineers to aid the utilization of this framework for application to different types of real-world problems.

The main aim of the paper is to establish the crossing numbers of the join products of the paths and the cycles on n vertices with a connected graph on five vertices isomorphic to the graph K1,1,3\e obtained by removing one edge e incident with some vertex of order two from the complete tripartite graph K1,1,3. The proofs are done with the help of well-known exact values for the crossing numbers of the join products of subgraphs of the considered graph with paths and cycles. Finally, by adding some edges to the graph under consideration, we obtain the crossing numbers of the join products of other graphs with the paths and the cycles on n vertices.

Let [Formula: see text] be a Montesinos link [Formula: see text] with positive rational numbers [Formula: see text] and [Formula: see text], each less than 1, and [Formula: see text] the minimal crossing number of [Formula: see text]. Herein, we construct arc presentations of [Formula: see text] with [Formula: see text], [Formula: see text] and [Formula: see text] arcs under some conditions for [Formula: see text], [Formula: see text] and [Formula: see text]. Furthermore, we determine the arc index of infinitely many Montesinos links.

In this paper, we improve the lower bound on the minimum number of &nbsp, ≤k-edges in sets of n points in general position in the plane when k is close to n2. As a consequence, we improve the current best lower bound of the rectilinear crossing number of the complete graph Kn for some values of n.

A surprising result of Bokal et al. proved that the exact minimum value of c such that c-crossing-critical graphs do not have bounded maximum degree is \(c=13\). The key to the result is an inductive construction of a family of 13-crossing-critical graphs with many vertices of arbitrarily high degrees. While the inductive part of the construction is rather easy, it all relies on the fact that a certain 17-vertex base graph has the crossing number 13, which was originally verified only by a machine-readable computer proof. We now provide a relatively short self-contained computer-free proof.

In 1930, Kuratowski showed that $K_{3,3}$ and $K_5$ are the only two minor-minimal non-planar graphs. Robertson and Seymour extended finiteness of the set of forbidden minors for any surface. \v{S}ir\'{a}\v{n} and Kochol showed that there are infinitely many $k$-crossing-critical graphs for any $k\ge 2$, even if restricted to simple $3$-connected graphs. Recently, $2$-crossing-critical graphs have been completely characterized by Bokal, Oporowski, Richter, and Salazar. We present a simplified description of large 2-crossing-critical graphs and use this simplification to count Hamiltonian cycles in such graphs. We generalize this approach to an algorithm counting Hamiltonian cycles in all 2-tiled graphs, thus extending the results of Bodro\v{z}a-Panti\'c, Kwong, Doroslova\v{c}ki, and Panti\'c for $n = 2$., Comment: 19 pages

Thomassen showed in 1978 that every planar hypohamiltonian graph contains a cubic vertex. Equivalently, a planar graph with minimum degree at least 4 in which every vertex‐deleted subgraph is hamiltonian, must be itself hamiltonian. By applying work of Brinkmann and the author, we extend this result in three directions. We prove that (i) every planar hypohamiltonian graph contains at least four cubic vertices, (ii) every planar almost hypohamiltonian graph contains a cubic vertex, which is not the exceptional vertex (solving a problem of the author raised in J. Graph Theory [79 (2015) 63–81]), and (iii) every hypohamiltonian graph with crossing number 1 contains a cubic vertex. Furthermore, we settle a recent question of Thomassen by proving that asymptotically the ratio of the minimum number of cubic vertices to the order of a planar hypohamiltonian graph vanishes.

We give an explicit extension of Spencer’s result on the biplanar crossing number of the Erdős–Renyi random graph G ( n , p ) . In particular, we show that the k -planar crossing number of G ( n , p ) is almost surely Ω ( ( n 2 p ) 2 ) . Along the same lines, we prove that for any fixed k , the k -planar crossing number of various models of random d -regular graphs is Ω ( ( d n ) 2 ) for d > c 0 for some constant c 0 = c 0 ( k ) .

Archdeacon (1987) proved that graphs embeddable on a fixed surface can be $3$-coloured so that each colour class induces a subgraph of bounded maximum degree. Edwards, Kang, Kim, Oum and Seymour (2015) proved that graphs with no $K_{t+1}$-minor can be $t$-coloured so that each colour class induces a subgraph of bounded maximum degree. We prove a common generalisation of these theorems with a weaker assumption about excluded subgraphs. This result leads to new defective colouring results for several graph classes, including graphs with linear crossing number, graphs with given thickness (with relevance to the earth-moon problem), graphs with given stack- or queue-number, linklessly or knotlessly embeddable graphs, graphs with given Colin de Verdi\`ere parameter, and graphs excluding a complete bipartite graph as a topological minor.

There are only few results concerning the crossing numbers of join of some graphs. In this paper, the crossing numbers of join products for the generalized Petersen graph P(3, 1) with n isolated vertices as well as with the path Pn on n vertices and with the cycle Cn are determined.

We investigate the terminal-pairibility problem in the case when the base graph is a complete bipartite graph, and the demand graph is also bipartite with the same color classes. We improve the lower bound on maximum value of $\Delta(D)$ which still guarantees that the demand graph $D$ is terminal-pairable in this setting. We also prove a sharp theorem on the maximum number of edges such a demand graph can have., Comment: 8 pages, several typos corrected

A new explicit relationship between spanning trees and recurrent configurations of a graph is given by constructing subtree. Applying this relationship, we determine the total number of topplings in an avalanche. As applications, we calculate the sizes of avalanches of the Abelian sandpile model on the complete graph, the wheel and the complete bipartite graph.

Inspired by previous work of Balogh (2006), we show that, given r ≥ 5 and n large, the balanced complete bipartite graph K n ∕ 2 , n ∕ 2 is the n -vertex graph that admits the largest number of r -edge-colorings for which there is no triangle whose edges are assigned three distinct colors. Moreover, we extend this result to lower values of n when r ≥ 10 , and we provide approximate results for r ∈ { 3 , 4 } .

We transfer Tutte’s theory for analyzing the chromatic number of a graph using nowhere-zero-coflows and -flows (NZ-flows) to the dichromatic number of a digraph and define Neumann-Lara-flows (NL-flows). We prove that any digraph whose underlying (multi-)graph is 3 -edge-connected admits a NL-3-flow, and even a NL-2-flow in case the underlying graph is 4 -edge connected. We conjecture that 3 -edge-connectivity already guarantees the existence of a NL-2-flow, which, if true, would imply the 2-Color-Conjecture for planar graphs due to Victor Neumann-Lara. Finally we present an extension of the theory to oriented matroids.

Assuming P ≠ N P , we show that if there is a constant-factor polynomial c-approximation algorithm for Crossing Number, then c ≥ 2 − 16 17 ≈ 1.058824 . Adding the Unique Games Conjecture to the hypotheses, then c ≥ 2 − α ≈ 1.121433 , where α is the approximation ratio of the algorithm for Maximum Cut by Goemans and Williamson.

The local crossing number of a drawing of a graph is the largest number of crossings on any edge of the drawing. In a rectilinear drawing of a graph, the vertices are points in the plane in general position and the edges are straight-line segments. The rectilinear local crossing number of the complete graph K n , denoted by lcr ‾ ( K n ) , is the minimum local crossing number over all rectilinear drawings of K n . We determine lcr ‾ ( K n ) . More precisely, for every n ∉ { 8 , 14 } , lcr ‾ ( K n ) = ⌈ 1 2 ( n − 3 − ⌈ n − 3 3 ⌉ ) ⌈ n − 3 3 ⌉ ⌉ , lcr ‾ ( K 8 ) = 4 , and lcr ‾ ( K 14 ) = 15 .

In this paper, we show the values of crossing numbers for join products of graph G on five vertices with the discrete graph Dn and the path Pn on n vertices. The proof is done with the help of software. The software generates all cyclic permutations for a given number n. For cyclic permutations, P1 – Pm will create a graph in which to calculate the distances between all vertices of the graph. These distances are used in proof of crossing numbers of presented graphs.

We give a polynomial-time algorithm to decide whether a connected bipartite graph admits a two-layer drawing in the plane such that a specified subset of pairs of disjoint edges cross. We consider the problem of deciding whether there exists such a drawing in which a specified subset of triples of pairwise crossing edges are concurrent. We give a necessary condition for the same and conjecture that it is sufficient.

We give a new proof of the fact that every planar graph is 5-choosable, and use it to show that every graph drawn in the plane so that the distance between every pair of crossings is at least 15 is 5-choosable. At the same time we may allow some vertices to have lists of size four only, as long as they are far apart and far from the crossings., 55 pages, 11 figures; minor revision according to the referee suggestions

The crossing number ${\mbox {cr}}(G)$ of a graph $G=(V,E)$ is the smallest number of edge crossings over all drawings of $G$ in the plane. For any $k\ge 1$, the $k$-planar crossing number of $G$, ${\mbox {cr}}_k(G)$, is defined as the minimum of ${\mbox {cr}}(G_1)+{\mbox {cr}}(G_2)+\ldots+{\mbox {cr}}(G_{k})$ over all graphs $G_1, G_2,\ldots, G_{k}$ with $\cup_{i=1}^{k}G_i=G$. Pach et al. [\emph{Computational Geometry: Theory and Applications} {\bf 68} 2--6, (2018)] showed that for every $k\ge 1$, we have ${\mbox {cr}}_k(G)\le \left(\frac{2}{k^2}-\frac1{k^3}\right){\mbox {cr}}(G)$ and that this bound does not remain true if we replace the constant $\frac{2}{k^2}-\frac1{k^3}$ by any number smaller than $\frac1{k^2}$. We improve the upper bound to $\frac{1}{k^2}(1+o(1))$ as $k\rightarrow \infty$. For the class of bipartite graphs, we show that the best constant is exactly $\frac{1}{k^2}$ for every $k$. The results extend to the rectilinear variant of the $k$-planar crossing number., Comment: 13 pages, 1 figure, 1 table

The crossing number of a graph G is the minimum number of edge crossings over all drawings of G in the plane. A graph G is k-crossing-critical if its crossing number is at least k, but if we remove any edge of G, its crossing number drops below k. There are examples of k-crossing-critical graphs that do not have drawings with exactly k crossings. Richter and Thomassen proved in 1993 that if G is k-crossing-critical, then its crossing number is at most \(2.5k+16\). We improve this bound to \(2k+6\sqrt{k}+47\).

We consider the construction of a polygon P with n vertices whose turning angles at the vertices are given by a sequence \(A=(\alpha _0,\ldots , \alpha _{n-1})\), \(\alpha _i\in (-\pi ,\pi )\), for \(i\in \{0,\ldots , n-1\}\). The problem of realizing A by a polygon can be seen as that of constructing a straight-line drawing of a graph with prescribed angles at vertices, and hence, it is a special case of the well studied problem of constructing an angle graph. In 2D, we characterize sequences A for which every generic polygon \(P\subset \mathbb {R}^2\) realizing A has at least c crossings, for every \(c\in \mathbb {N}\), and describe an efficient algorithm that constructs, for a given sequence A, a generic polygon \(P\subset \mathbb {R}^2\) that realizes A with the minimum number of crossings. In 3D, we describe an efficient algorithm that tests whether a given sequence A can be realized by a (not necessarily generic) polygon \(P\subset \mathbb {R}^3\), and for every realizable sequence the algorithm finds a realization.

Graph Crossing Number is a fundamental and extensively studied problem with wide ranging applications. In this problem, the goal is to draw an input graph $G$ in the plane so as to minimize the number of crossings between the images of its edges. The problem is notoriously difficult, and despite extensive work, non-trivial approximation algorithms are only known for bounded-degree graphs. Even for this special case, the best current algorithm achieves a $\tilde{O}(\sqrt{n})$ -approximation, while the best current negative results do not rule out constant-factor approximation. All current approximation algorithms for the problem build on the same paradigm, which is also used in practice: compute a set $E^{\prime}$ of edges (called a planarizing set) such that $G\ \backslash\ E^{\prime}$ is planar; compute a planar drawing of $G\ \backslash\ E^{\prime}$ ; then add the drawings of the edges of $E^{\prime}$ to the resulting drawing. Unfortunately, there are examples of graphs $G$ , in which any implementation of this method must incur $\Omega$ (OPT2) crossings, where OPT is the value of the optimal solution. This barrier seems to doom the only currently known approach to designing approximation algorithms for the problem, and to prevent it from yielding a better than $O(\sqrt{n})$ -approximation. In this paper we propose a new paradigm that allows us to overcome this barrier. We show an algorithm, that, given a bounded-degree graph G and a planarizing E' set of its edges, computes another planarizing edge set E" with E' ⊆ E", such that |E"| is relatively small, and there exists a near-optimal drawing of in which no edges of participate in crossings. This allows us to reduce the Crossing Number problem to Crossing Number with Rotation System – a variant of the Crossing Number problem, in which the ordering of the edges incident to every vertex is fixed as part of input. In our reduction, we obtain an instance of this problem, where is roughly bounded by the crossing number of the original graph. We show a randomized algorithm for this new problem, that allows us to obtain an - approximation for Graph Crossing Number on bounded-degree graphs, for some constant.

We call a multigraph non-homotopic if it can be drawn in the plane in such a way that no two edges connecting the same pair of vertices can be continuously transformed into each other without passing through a vertex, and no loop can be shrunk to its end-vertex in the same way. It is easy to see that a non-homotopic multigraph on \(n>1\) vertices can have arbitrarily many edges. We prove that the number of crossings between the edges of a non-homotopic multigraph with n vertices and \(m>4n\) edges is larger than \(c\frac{m^2}{n}\) for some constant \(c>0\), and that this bound is tight up to a polylogarithmic factor. We also show that the lower bound is not asymptotically sharp as n is fixed and \(m\longrightarrow \infty \).

Hill's Conjecture states that the crossing number $\text{cr}(K_n)$ of the complete graph $K_n$ in the plane (equivalently, the sphere) is $\frac{1}{4}\lfloor\frac{n}{2}\rfloor\lfloor\frac{n-1}{2}\rfloor\lfloor\frac{n-2}{2}\rfloor\lfloor\frac{n-3}{2}\rfloor=n^4/64 + O(n^3)$. Moon proved that the expected number of crossings in a spherical drawing in which the points are randomly distributed and joined by geodesics is precisely $n^4/64+O(n^3)$, thus matching asymptotically the conjectured value of $\text{cr}(K_n)$. Let $\text{cr}_P(G)$ denote the crossing number of a graph $G$ in the projective plane. Recently, Elkies proved that the expected number of crossings in a naturally defined random projective plane drawing of $K_n$ is $(n^4/8\pi^2)+O(n^3)$. In analogy with the relation of Moon's result to Hill's conjecture, Elkies asked if $\lim_{n\to\infty} \text{cr}_P(K_n)/n^4=1/8\pi^2$. We construct drawings of $K_n$ in the projective plane that disprove this.

We introduce a model for random geodesic drawings of the complete bipartite graph \(K_{n,n}\) on the unit sphere \(\mathbb {S}^2\) in \(\mathbb {R}^3\), where we select the vertices in each bipartite class of \(K_{n,n}\) with respect to two non-degenerate probability measures on \(\mathbb {S}^2\). It has been proved recently that many such measures give drawings whose crossing number approximates the Zarankiewicz number (the conjectured crossing number of \(K_{n,n}\)). In this paper we consider the intersection graphs associated with such random drawings. We prove that for any probability measures, the resulting random intersection graphs form a convergent graph sequence in the sense of graph limits. The edge density of the limiting graphon turns out to be independent of the two measures as long as they are antipodally symmetric. However, it is shown that the triangle densities behave differently. We examine a specific random model, blowups of antipodal drawings D of \(K_{4,4}\), and show that the triangle density in the corresponding crossing graphon depends on the angles between the great circles containing the edges in D and can attain any value in the interval \(\bigl (\frac{83}{12288}, \frac{128}{12288}\bigr )\).

A tripartite-circle drawing of a tripartite graph is a drawing in the plane, where each part of a vertex partition is placed on one of three disjoint circles, and the edges do not cross the circles. We present upper and lower bounds on the minimum number of crossings in tripartite-circle drawings of $K_{m,n,p}$. In contrast to 1- and 2-circle drawings, which may attain the Harary-Hill bound, our results imply that balanced restricted 3-circle drawings of the complete graph are not optimal., 21 pages, 13 figures. arXiv:1910.06963v1 was split into doi:10.1002/jgt.22763=arXiv:1910.06963v2 and arXiv:2108.01032, with K22n result in the latter. Removed K22n from JGT abstract to reflect the published JGT paper