Results 291 to 300 of about 1,286,422 (323)

Applications of the crossing number

Algorithmica, 1994
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
János Pach, János Pach, Farhad Shahrokhi, Mario Szegedy   +3 more
openaire   +4 more sources

On stable crossing numbers

Journal of Graph Theory, 1978
AbstractResults giving the exact crossing number of an infinite family of graphs on some surface are very scarce. In this paper we show the following: for G = Qn × K4.4, cry(G)‐m(G) = 4m, for 0 ⩽ = m ⩽ 2n. A generalization is obtained, for certain repeated cartesian products of bipartite graphs. Nonorientable analogs are also developed.
Paul C. Kainen, Arthur T. White
openaire   +2 more sources

THE ADDITIVITY OF CROSSING NUMBERS [PDF]

Journal of Knot Theory and Its Ramifications, 2004
It has long been conjectured that the crossing numbers of links are additive under the connected sum of links. This is a difficult problem in knot theory and has been open for more than 100 years. In fact, many questions of much weaker conditions are still open.
openaire   +1 more source

On the parity of crossing numbers

Journal of Graph Theory, 1988
AbstractFor an integer n ⩾ 1, a graph G has an n‐constant crossing number if, for any two good drawings ϕ and ϕ′ of G in the plane, μ(ϕ) ≡ μ(ϕ′) (mod n), where μ(ϕ) is the number of crossings in ϕ. We prove that, except for trivial cases, a graph G has n‐constant crossing number if and only if n = 2 and G is either Kp or Kq,r, where p, q, and r are odd.
R. Bruce Richter, Dan Archdeacon
openaire   +3 more sources

Crossing Number Problems

The American Mathematical Monthly, 1973
(1973). Crossing Number Problems. The American Mathematical Monthly: Vol. 80, No. 1, pp. 52-58.
Richard K. Guy, Paul Erdös
openaire   +2 more sources

The crossing number of posets

Order, 1994
Given a finite poset \(P\) represented by a continuous function \(\xi= \{f_ x\}_{x\in P}\) on \([0,1]\) whose graphs \(G(f_ x)\) have certain intersection properties and such that ...
openaire   +2 more sources

Ribbon crossing numbers, crossing numbers, and Alexander polynomials

Topology and its Applications, 2018
Abstract A 2-knot is a surface in R 4 that is homeomorphic to S 2 , the standard sphere in 3-space. A ribbon 2-knot is a 2-knot obtained from m 2-spheres in R 4 by connecting them with m − 1 annuli. Let K 2 be a ribbon 2-knot. The ribbon crossing number, denoted by r- c r ( K 2 )
openaire   +2 more sources

Crossing Number and Weighted Crossing Number of Near-Planar Graphs

Algorithmica, 2009
A nonplanar graph G is near-planar if it contains an edge e such that G−e is planar. The problem of determining the crossing number of a near-planar graph is exhibited from different combinatorial viewpoints. On the one hand, we develop min-max formulas involving efficiently computable lower and upper bounds.
Sergio Cabello, Bojan Mohar
openaire   +1 more source

The book crossing number of a graph

Journal of Graph Theory, 1996
The book crossing number of a graph \(G\) is the minimum number of edge crossings when the vertices of \(G\) are placed on the spine of a \(k\)-page book and the edges of \(G\) are drawn on the pages, such that each edge is contained in one page. The authors give two polynomial time approximation algorithms and prove bounds for the crossing number.
Imrich Vrto, László A. Székely, Farhad Shahrokhi, Ondrej Sýkora   +3 more
openaire   +3 more sources