Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 15 of 15 for “"crossing numbers"”.
-
Some Results on Crossing Numbers
… to produce the minimum number of edge crossings for a complete graph, which is its crossing number. This dissertation proves that no edge in this drawing can be redrawn to reduce the total number of edge crossings.
-
On the Crossing Numbers of Complete Graphs
… the next step toward Guy's Conjecture that the crossing number of <em>K<sub>n</sub></em> is $(1/4)[n/2][(n-1)/2][(n-2)/2][(n-3)/2]$. We show that the conjecture is true for <em>n</em> = 11,12; previously the conjecture was known to be true for <em>n</em> ≤ 10. We also prove several minor …
-
Knotted fields and real algebraic links
… their classification.<br/><br/>We also study the crossing numbers of composite knots and relate them to crossing numbers of spatial graphs. The resulting connections are expected to lead to a new approach to the conjecture of the additivity of the crossing number.
-
On 4-Regular Planar Hamiltonian Graphs
In order to research knots with large crossing numbers, one would like to be able to select a random knot from the set of all knots with n crossings with as close to uniform probability as possible. The underlying graph of a knot diagram can be viewed as a 4-regular planar graph. The existence of a …
-
Hypohamiltonian and almost hypohamiltonian graphs
… and hypohamiltonian graphs in the context of crossing numbers. Chapter 3 is a thorough discussion of the newly introduced almost hypohamiltonian graphs and their connection to hypohamiltonian graphs. Once more, the planar case plays an exceptional role. At the end of the chapter, we study …
-
Highly Non-Convex Crossing Sequences
For a given graph, G, the crossing number crₐ(G) denotes the minimum number of edge crossings when a graph is drawn on an orientable surface of genus a. The sequence cr₀(G), cr₁(G), ... is said to be the crossing sequence of a G. An equivalent definition exists for non-orientable surfaces. In 1983, …
-
A Few Problems on the Steiner Distance and Crossing Number of Graphs
… properties of graphs in the context of crossing numbers. For positive integers n and e, let κ(n, e) be the minimum number of crossings among all graphs with n vertices and at least e edges. Under the condition that n << e << n2, Pach, Spencer, and Tóth [Discrete and Computational …
-
On 2-crossing-critical graphs with a V8-minor
The crossing number of a graph is the minimum number of pairwise edge crossings in a drawing of a graph. A graph $G$ is $k$-crossing-critical if it has crossing number at least $k$, and any subgraph of $G$ has crossing number less than $k$. A consequence of Kuratowski's theorem is that 1-critical …
-
Tangled up in Tanglegrams
… its roots, we will prove that the Tanglegram crossing number of the original Tanglegram is greater than or equal to the crossing number of the augmented Tanglegram taken as a graph. We will show that the removal of a matching edge from a Tanglegram of size n ≥3 decreases the Tanglegram …
-
Rectilinear Crossing Number of Graphs Excluding a Single-Crossing Graph as a Minor
The crossing number of a graph 𝐺 is the minimum number of crossings in any drawing of 𝐺 in the plane. The rectilinear crossing number of 𝐺 is the minimum number of crossings in any straight-line drawing of 𝐺. The Fáry-Wagner theorem states that planar graphs have rectilinear crossing number zero. …
-
On Geometric Drawings of Graphs
… rectilinear drawing preserving the set of crossing pairs of edges. We show that, under some circumstances, pseudolinearity is a necessary and sufficient condition for the existence of such transformation. For this, we prove a generalization of Tutte's Spring Theorem for drawings with …