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"”.

  1. 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.

    penn Repository record for Some Results on Crossing Numbers (opens in a new tab)

  2. 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> &le; 10. We also prove several minor …

    waterloo Repository record for On the Crossing Numbers of Complete Graphs (opens in a new tab)

  3. 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.

    bristol Repository record for Knotted fields and real algebraic links (opens in a new tab) Download PDF for Knotted fields and real algebraic links (opens in a new tab)

  4. 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 …

    wku-diss Repository record for On 4-Regular Planar Hamiltonian Graphs (opens in a new tab)

  5. 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 …

    ghent Repository record for Hypohamiltonian and almost hypohamiltonian graphs (opens in a new tab)

  6. 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, …

    waterloo Repository record for Highly Non-Convex Crossing Sequences (opens in a new tab)

  7. 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 …

    south-carolina Repository record for A Few Problems on the Steiner Distance and Crossing Number of Graphs (opens in a new tab)

  8. 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 …

    waterloo Repository record for On 2-crossing-critical graphs with a V8-minor (opens in a new tab)

  9. 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 …

    south-carolina Repository record for Tangled up in Tanglegrams (opens in a new tab)

  10. 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. …

    ottawa-retro Repository record for Rectilinear Crossing Number of Graphs Excluding a Single-Crossing Graph as a Minor (opens in a new tab)

  11. 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 …

    waterloo Repository record for On Geometric Drawings of Graphs (opens in a new tab)