Results 41 to 50 of about 1,286,422 (323)
Crossing number, pair-crossing number, and expansion
Journal of Combinatorial Theory, Series B, 2004 The crossing number \(\text{cr}(G)\) of a graph \(G\) is the minimum possible number of edge crossings in a drawing of \(G\) in the plane, and the pair-crossing number \( \text{pcr}(G)\) of a graph \(G\) is smallest number of pairs of crossing edges in any drawing of \(G\) in the plane.
Petr Kolman, Jiří Matoušek
openaire +2 more sources
Crossing Numbers of Join Product with Discrete Graphs: A Study on 6-Vertex Graphs
Mathematics, 2023 Reducing the number of crossings on graph edges can be useful in various applications, including network visualization, circuit design, graph theory, cartography or social choice theory.
Jana Fortes, Michal Staš
doaj +1 more source
On the crossing numbers of join products of five graphs of order six with the discrete graph [PDF]
Opuscula Mathematica, 2020 The main purpose of this article is broaden known results concerning crossing numbers for join of graphs of order six. We give the crossing number of the join product \(G^{\ast} + D_n\), where the disconnected graph \(G^{\ast}\) of order six consists of ...
Michal Staš
doaj +1 more source
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
ALTERNATIVE PROOF ON THE CROSSING NUMBER OF K1,1,3,N [PDF]
Acta Electrotechnica et Informatica, 2019 The main aim of the paper is to give the crossing number of join product G+Dn for the connected graph G of order five isomorphic with the complete tripartite graph K1,1,3, where Dn consists on n isolated vertices.
Michal STAS
doaj +1 more source
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
Improvement on the Crossing Number of Crossing-Critical Graphs [PDF]
Discrete & Computational Geometry, 2020 AbstractThe 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.
János Barát +4 more
openaire +6 more sources
Proceedings of the twenty-seventh annual symposium on Computational geometry, 2011 We define a variant of the crossing number for an embedding of a graphGinto ℝ3, and prove a lower bound on it which almost implies the classical crossing lemma. We also give sharp bounds on the rectilinear space crossing numbers of pseudo-random graphs.
Alfredo Hubard, Boris Bukh
openaire +4 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
Parity Properties of Configurations
Mathematics, 2022 In the paper, the crossing number of the join product G*+Dn for the disconnected graph G* consisting of two components isomorphic to K2 and K3 is given, where Dn consists of n isolated vertices.
Michal Staš
doaj +1 more source