Results 31 to 40 of about 1,312,414 (329)
Discrete Mathematics & Theoretical Computer Science, 2005 An edge in a drawing of a graph is called $\textit{even}$ if it intersects every other edge of the graph an even number of times. Pach and Tóth proved that a graph can always be redrawn such that its even edges are not involved in any intersections.
Michael J. Pelsmajer +2 more
doaj +1 more source
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
openaire +1 more source
The Bundled Crossing Number [PDF]
, 2016 Appears in the Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD 2016)
Alam, M. J., Fink, M., Pupyrev, S.
openaire +3 more sources
From Local Pair-Crossing Number to Local Crossing Number
We prove that if a graph can be drawn in the plane such that each edge crosses at most k other edges, then it can be redrawn so that each edge participates in at most k³+O(k²) crossings. This improves the previous exponential bound that follows from a result of Schaefer and Štefankovič and answers a question of Ackerman and Schaefer.
Fox, Jacob, Pach, János, Suk, Andrew
openalex +3 more sources
The Crossing Number of Cartesian Product of 5-Wheel with any Tree
Discussiones Mathematicae Graph Theory, 2021 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.
Wang Yuxi, Huang Yuanqiu
doaj +1 more source
Graphs and Combinatorics, 2018 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Ku, Cheng Yeaw, Wong, Kok Bin
openaire +3 more sources
Approximating the Bundled Crossing Number
Journal of Graph Algorithms and Applications, 2022 Bundling crossings is a strategy which can enhance the readability of graph drawings. In this paper we consider good drawings, i.e., we require that any two edges have at most one common point which can be a common vertex or a crossing. Our main result is that there is a polynomial-time algorithm to compute an 8-approximation of the bundled ...
Arroyo, Alan, Felsner, Stefan
openaire +2 more sources
The Crossing Number of Join of a Special Disconnected 6-Vertex Graph with Cycle
Mathematics, 2023 The crossing number of a graph G, cr(G), is defined as the smallest possible number of edge-crossings in a drawing of G in the plane. There are almost no results concerning crossing number of join of a disconnected 6-vertex graph with cycle. The main aim
Zongpeng Ding, Xiaomei Qian
doaj +1 more source
Crossing numbers of composite knots and spatial graphs [PDF]
, 2018 We study the minimal crossing number $c(K_{1}\# K_{2})$ of composite knots $K_{1}\# K_{2}$, where $K_1$ and $K_2$ are prime, by relating it to the minimal crossing number of spatial graphs, in particular the $2n$-theta curve $\theta_{K_{1},K_{2}}^n$ that
Bode, Benjamin
core +3 more sources
Embeddings and immersions of tropical curves [PDF]
, 2015 We construct immersions of trivalent abstract tropical curves in the Euclidean plane and embeddings of all abstract tropical curves in higher dimensional Euclidean space.
Cartwright, Dustin +3 more
core +1 more source