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 14 of 14 for “"plane graphs"”.

  1. Testing vertex connectivity of bowtie 1-plane graphs

    … sets and separating cycles from planar graphs to the class of bowtie 1-plane graphs. These are graphs that are embedded on the plane such that each edge is crossed at most once by another edge, and the endpoints of each such crossing induce either $K_4$, $K_4 \setminus \{e\}$ or $C_4$. …

    waterloo Repository record for Testing vertex connectivity of bowtie 1-plane graphs (opens in a new tab)

  2. Almost Regular Graphs And Edge Face Colorings Of Plane Graphs

    Regular graphs are graphs in which all vertices have the same degree. Many properties of these graphs are known. Such graphs play an important role in modeling network configurations where equipment limitations impose a restriction on the maximum number of links emanating from a node. These …

    ucf Repository record for Almost Regular Graphs And Edge Face Colorings Of Plane Graphs (opens in a new tab)

  3. Edge coloring of simple graphs and edge -face coloring of simple plane graphs

    … generalizes earlier results.;Given a simple plane graph G, an edge-face k-coloring of G is a function &phis; : E(G) ∪ F(G) {lcub}1, ···, k{rcub} such that, for any two adjacent elements a, b ∈ E(G) ∪ F(G), &phis;( a) ≠ &phis;(b). Denote chie( G), chief(G), Delta( G) the edge chromatic number, …

    wvu Repository record for Edge coloring of simple graphs and edge -face coloring of simple plane graphs (opens in a new tab)

  4. Bounds on Maximum Matchings in 1-Planar Graphs

    … lower bounds on maximum matchings in 1-planar graphs. We expand upon the tools used for proofs of matching bounds in other classes of graphs as well as some original ideas in order to find these bounds. The first novel results we provide are lower bounds on maximum matchings in 1-planar graphs …

    waterloo Repository record for Bounds on Maximum Matchings in 1-Planar Graphs (opens in a new tab)

  5. Combinatorial presentations of string diagrams for non-symmetric monoidal categories

    … of two wires across each other. While abstract graphs provide a suitable combinatorial structure for string diagrams of symmetric monoidal categories, they are not sufficient in our case and we will extend the framework to surface-embedded graphs to be able to capture the absence of symmetry in …

    strathclyde Repository record for Combinatorial presentations of string diagrams for non-symmetric monoidal categories (opens in a new tab)

  6. Planar Open Rectangle-of-Influence Drawings

    … weak RI-drawing, not even for inner triangulated graphs. In this thesis, we have two major contributions. First we study open weak RI-drawings of plane graphs that must have a non-aligned frame, i.e., the graph obtained from removing the interior of every filled triangle is drawn such that no two …

    waterloo Repository record for Planar Open Rectangle-of-Influence Drawings (opens in a new tab)

  7. Distances in planar graphs

    … diameter can have. The face-degree of a face in plane graph is the length of the shortest closed walk traversing the boundary of the face. A plane graph is ρ-face-degree regular if every face has face-degree ρ. This thesis begins with a literature review outlining the results and methods of …

    cape-town Repository record for Distances in planar graphs (opens in a new tab)

  8. Face Routing with Guaranteed Message Delivery in Wireless Ad-hoc Networks

    … guarantees message delivery in static connected plane graphs. However, a static connected plane graph is often difficult to obtain in a real wireless network. This thesis extends face routing to more realistic models of wireless ad-hoc networks. We present a new version of face routing that …

    toronto-retro Repository record for Face Routing with Guaranteed Message Delivery in Wireless Ad-hoc Networks (opens in a new tab)

  9. Facial Nonrepetitive Graph Colourings

    … vertices on the boundary walk of a face of a plane graph G. A nonrepetitive facial colouring of G is a vertex colouring such that the sequence of colours of any facial path is nonrepetitive, and the minimum number of colours required for such a colouring is the facial Thue chromatic number of …

    carleton Repository record for Facial Nonrepetitive Graph Colourings (opens in a new tab)

  10. Simple, Faster Kinetic Data Structures

    … graph. • The first KDS to consider maintaining plane graphs on moving points. • The first KDS for maintenance of all the k-nearest neighbors, for any k ≥ 1. • The first KDS to answer the reverse k-nearest neighbor queries, for any k ≥ 1 in any fixed dimension, on a set of moving points.

    uvic Repository record for Simple, Faster Kinetic Data Structures (opens in a new tab)

  11. Distance Between Crossing Edges: A New Measure for Beyond-Planarity

    Planar graphs—which are graphs that can be drawn without edge-crossings—are an important class of graphs, both from a theoretical and from an algorithmic perspective. They often admit elegant structures and efficient algorithms that are otherwise infeasible for general graphs. While planar graphs …

    carleton Repository record for Distance Between Crossing Edges: A New Measure for Beyond-Planarity (opens in a new tab)

  12. BLINK : a language to view; Recognize; Classify and manipulate 3D-spaces

    Um blink é um grafo plano onde cada aresta ou é vermelha ou é verde. Um espaço 3D ou, simplesmente, um espaço é uma variedade 3-dimensional conexa, fechada e orientada. Neste trabalho exploramos pela primeira vez em maiores detalhes o fato de que todo blink induz um espaço e todo espaço é induzido …

    brazil-ufpe Repository record for BLINK : a language to view; Recognize; Classify and manipulate 3D-spaces (opens in a new tab)

  13. Flips & Partitions in Geometric Graphs

    … geometry. The first being related to plane graphs, one of the most widely studied themes in various disciplines related to graph drawing. The second part is concerned with reconfiguraton problems, a fundamental field with increasing popularity. Edge partitions of complete geometric …

    fu-berlin Repository record for Flips & Partitions in Geometric Graphs (opens in a new tab)

  14. Tightening curves and graphs on surfaces

    … homotopy moves and a set of local operations on graphs called electrical transformations. Electrical transformations have been used to simplify electrical networks since the 19th century; later they have been used for solving various combinatorial problems on graphs, as well as applications in …

    uiuc Repository record for Tightening curves and graphs on surfaces (opens in a new tab)