Results 1 to 10 of about 295,074 (120)
The Degenerate Crossing Number and Higher-Genus Embeddings
Journal of Graph Algorithms and Applications, 2022 If a graph embeds in a surface with $k$ crosscaps, does it always have an embedding in the same surface in which every edge passes through each crosscap at most once?
Marcus Schaefer, Daniel Štefankovič
doaj +1 more source
Approximating the Bundled Crossing Number
Journal of Graph Algorithms and Applications, 2023 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.
Alan Arroyo, Stefan Felsner
doaj +1 more source
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 +1 more source
Properties of Large 2-Crossing-Critical Graphs
Journal of Graph Algorithms and Applications, 2022 A $c$-crossing-critical graph is one that has crossing number at least $c$ but each of its proper subgraphs has crossing number less than $c$. Recently, a set of explicit construction rules was identified by Bokal, Oporowski, Richter, and Salazar to ...
Drago Bokal +6 more
doaj +1 more source
Complexity of Geometric k-Planarity for Fixed k
Journal of Graph Algorithms and Applications, 2021 The rectilinear local crossing number, $\mathop{\overline{\rm lcr}}(G)$, of a graph $G$ is the smallest $k$ so that $G$ has a straight-line drawing with at most $k$ crossings along each edge. We show that deciding whether $\mathop{\overline{\rm lcr}}(G)
Marcus Schaefer
doaj +1 more source
Counting Hamiltonian Cycles in 2-Tiled Graphs
Mathematics, 2021 In 1930, Kuratowski showed that K3,3 and K5 are the only two minor-minimal nonplanar graphs. Robertson and Seymour extended finiteness of the set of forbidden minors for any surface.
Alen Vegi Kalamar +2 more
doaj +1 more source
An Ongoing Project to Improve the Rectilinear and the Pseudolinear Crossing Constants
Journal of Graph Algorithms and Applications, 2020 A drawing of a graph in the plane is pseudolinear if the edges of the drawing can be extended to doubly-infinite curves that form an arrangement of pseudolines, that is, any pair of these curves crosses precisely once.
Oswin Aichholzer +4 more
doaj +1 more source
Maximum Cut Parameterized by Crossing Number
Journal of Graph Algorithms and Applications, 2020 Given an edge-weighted graph $G$ on $n$ nodes, the NP-hard $\rm{M\small{AX}}$-$\rm{C\small{UT}}$ problem asks for a node bipartition such that the sum of edge weights joining the different partitions is maximized.
Markus Chimani +5 more
doaj +1 more source
The crossing numbers of join products of eight graphs of order six with paths and cycles
Karpatsʹkì Matematičnì Publìkacìï, 2023 The crossing number $\mathrm{cr}(G)$ of a graph $G$ is the minimum number of edge crossings over all drawings of $G$ in the plane. The main aim of this paper is to give the crossing numbers of the join products of eight graphs on six vertices with paths ...
M. Staš
doaj +1 more source
On the crossing number for Kronecker product of a tripartite graph with path
AKCE International Journal of Graphs and Combinatorics, 2020 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 ...
N. Shanthini, J. Baskar Babujee
doaj +1 more source