On the k-planar local crossing number Asplund, John; Do, Thao; Hamm, Arran ...
Discrete mathematics,
April 2019, 2019-04-00, Letnik:
342, Številka:
4
Journal Article
Recenzirano
Odprti dostop
Given a fixed positive integer k, the k-planar local crossing number of a graph G, denoted by lcrk(G), is the minimum positive integer L such that G can be decomposed into k subgraphs, each of which ...can be drawn in a plane such that no edge is crossed more than L times. In this note, we show that under certain natural restrictions, the ratio lcrk(G)∕lcr1(G) is of order 1∕k2, which is analogous to the result of Pach et al. (2018) for the k-planar crossing number crk(G) (defined as the minimum positive integer C for which there is a k-planar drawing of G with C total edge crossings). As a corollary of our proof we show that, under similar restrictions, one may obtain a k-planar drawing of G with both the total number of edge crossings as well as the maximum number of times any edge is crossed essentially matching the best known bounds. Our proof relies on the crossing number inequality and several probabilistic tools such as concentration of measure and the Lovász local lemma.
In 1958, Hill conjectured that the minimum number of crossings in a drawing of
K
n
is exactly
Z
(
n
)
=
1
4
⌊
n
2
⌋
⌊
n
-
1
2
⌋
⌊
n
-
2
2
⌋
⌊
n
-
3
2
⌋
. Generalizing the result by Ábrego et al. for ...2-page book drawings, we prove this conjecture for plane drawings in which edges are represented by
x
-monotone curves. In fact, our proof shows that the conjecture remains true for
x
-monotone drawings of
K
n
in which adjacent edges may cross an even number of times, and instead of the crossing number we count the pairs of edges which cross an odd number of times. We further discuss a generalization of this result to shellable drawings, a notion introduced by Ábrego et al. We also give a combinatorial characterization of several classes of
x
-monotone drawings of complete graphs using a small set of forbidden configurations. For a similar local characterization of shellable drawings, we generalize Carathéodory’s theorem to simple drawings of complete graphs.
The crossing number of a graph G is the minimum number of edge-crossings over all drawings of G in the plane. Determining the crossing number of a graph is a well-known problem in combinatorics. One ...of its most studied variants is to restrict the minimum to all drawings of G whose edges are straight line segments. This minimum is known as the geometric crossing number of G. We determine the exact crossing number of centrally symmetric geometric drawings of the complete graph.
The crossing number of K5,n+1∖e Huang, Yuanqiu; Wang, Yuxi
Applied mathematics and computation,
07/2020, Letnik:
376
Journal Article
Recenzirano
Let K5,n+1∖e (n ≥ 0) denote the complete bipartite graph K5,n+1 with one edge deleted. In this paper, we show that the crossing number of K5,n+1∖e is n(n−1).
On the Pseudolinear Crossing Number Hernández‐Vélez, César; Leaños, Jesús; Salazar, Gelasio
Journal of graph theory,
March 2017, 2017-03-00, 20170301, Letnik:
84, Številka:
3
Journal Article
Recenzirano
Odprti dostop
A drawing of a graph is pseudolinear if there is a pseudoline arrangement such that each pseudoline contains exactly one edge of the drawing. The pseudolinear crossing number of a graph G is the ...minimum number of pairwise crossings of edges in a pseudolinear drawing of G. We establish several facts on the pseudolinear crossing number, including its computational complexity and its relationship to the usual crossing number and to the rectilinear crossing number. This investigation was motivated by open questions and issues raised by Marcus Schaefer in his comprehensive survey of the many variants of the crossing number of a graph.
Testing gap k-planarity is NP-complete Urschel, John C.; Wellens, Jake
Information processing letters,
August 2021, 2021-08-00, Letnik:
169
Journal Article
Recenzirano
Odprti dostop
•Show that testing k-planarity is NP-hard.•Prove that the stronger gap decision problem is NP-hard.•Show instances in which crossing number and local crossing number cannot be simultaneously ...approximately minimized.
For all k≥1, we show that deciding whether a graph is k-planar is NP-complete, extending the well-known fact that deciding 1-planarity is NP-complete. Furthermore, we show that the gap version of this decision problem is NP-complete. In particular, given a graph with local crossing number either at most k≥1 or at least 2k, we show that it is NP-complete to decide whether the local crossing number is at most k or at least 2k. This algorithmic lower bound proves the non-existence of a (2−ϵ)-approximation algorithm for any fixed k≥1. In addition, we analyze the sometimes competing relationship between the local crossing number (maximum number of crossings per edge) and crossing number (total number of crossings) of a drawing. We present results regarding the non-existence of drawings that simultaneously approximately minimize both the local crossing number and crossing number of a graph.
We present several general results about drawings of Kn, as a beginning to trying to determine its crossing number. As application, we give a complete proof that the crossing number of K9 is 36 and ...that all drawings in one large, natural class of drawings of K11 have at least 100 crossings.
It has long been known that the quadratic term in the degree of the colored Jones polynomial of a knot is bounded above in terms of the crossing number of the knot. We show that this bound is sharp ...if and only if the knot is adequate.
As an application of our result we determine the crossing numbers of broad families of non-adequate prime satellite knots. More specifically, we exhibit minimal crossing number diagrams for untwisted Whitehead doubles of zero-writhe adequate knots. This allows us to determine the crossing number of untwisted Whitehead doubles of any amphicheiral adequate knot, including, for instance, the Whitehead doubles of the connected sum of any alternating knot with its mirror image.
We also determine the crossing number of the connected sum of any adequate knot with an untwisted Whitehead double of a zero-writhe adequate knot.
PDF
