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"”.
-
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$. …
-
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 …
-
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, …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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.
-
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 …
-
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 …
-
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 …
-
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 …