Results 11 to 20 of about 1,286,422 (323)
On the pseudolinear crossing number [PDF]
Journal of Graph Theory, 2014 A drawing of a graph is {\em pseudolinear} if there is a pseudoline arrangement such that each pseudoline contains exactly one edge of the drawing. The {\em pseudolinear crossing number} of a graph $G$ is the minimum number of pairwise crossings of edges
Hernandez-Velez, Cesar +2 more
core +4 more sources
Analogies between the crossing number and the tangle crossing number [PDF]
The Electronic Journal of Combinatorics, 2017 Tanglegrams are special graphs that consist of a pair of rooted binary trees with the same number of leaves, and a perfect matching between the two leaf-sets.
Anderson, Robin +10 more
core +4 more sources
On the Maximum Crossing Number
Journal of Graph Algorithms and Applications, 2017 Research about crossings is typically about minimization. In this paper, we consider \emph{maximizing} the number of crossings over all possible ways to draw a given graph in the plane. Alpert et al. [Electron. J.
E Steinitz +18 more
core +4 more sources
Odd Crossing Number and Crossing Number Are Not the Same [PDF]
Discrete & Computational Geometry, 2008 The crossing number of a graph is the minimum number of edge intersections in a plane drawing of a graph, where each intersection is counted separately. If instead we count the number of pairs of edges that intersect an odd number of times, we obtain the odd crossing number. We show that there is a graph for which these two concepts differ, answering a
Michael J. Pelsmajer +2 more
openalex +5 more sources
Odd Crossing Number Is Not Crossing Number [PDF]
, 2006 The crossing number of a graph is the minimum number of edge intersections in a plane drawing of a graph, where each intersection is counted separately. If instead we count the number of pairs of edges that intersect an odd number of times, we obtain the odd crossing number. We show that there is a graph for which these two concepts differ, answering a
Michael J. Pelsmajer +2 more
openalex +3 more sources
Minor-monotone crossing number [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 The minor crossing number of a graph $G$, $rmmcr(G)$, is defined as the minimum crossing number of all graphs that contain $G$ as a minor. We present some basic properties of this new minor-monotone graph invariant.
Drago Bokal +2 more
doaj +3 more sources
Note on the Pair-crossing Number and the Odd-crossing Number [PDF]
Discrete & Computational Geometry, 2007 The crossing number ${\mbox{\sc cr}}(G)$ of a graph G is the minimum possible number of edge-crossings in a drawing of G, the pair-crossing number ${\mbox{\sc pair-cr}}(G)$ is the minimum possible number of crossing pairs of edges in a drawing of G, and the odd-crossing number ${\mbox{\sc odd-cr}}(G)$ is the minimum number of pairs of edges that cross ...
Gézá Tóth
openalex +4 more sources
An Evolutionary Formulation of the Crossing Number Problem [PDF]
Discrete Dynamics in Nature and Society, 2009 A graph drawing algorithm is presented which results in complete graphs having minimum crossings equal to that of Guy's conjecture. It is then generalized and formulated in an evolutionary algorithm (EA) to perform constrained search for the crossing ...
Che Sheng Gan +3 more
doaj +2 more sources
Journal of Combinatorial Theory, 1970 AbstractSeveral arguments are presented which provide restrictions on the possible number of crossings in drawings of bipartite graphs. In particular it is shown that cr(K5,n)=4[1/2n][1/2(n−1)] and cr(K6,n)=6[1/2n][1/2(n−1)].
Daniel J. Kleitman
openalex +4 more sources
Which Crossing Number Is It Anyway?
Journal of Combinatorial Theory, Series B, 2000 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
János Pach, Gézá Tóth
openalex +2 more sources