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 11 of 11 for “"Outerplanar Graph"”.

  1. A 2-Approximation for the Height of Maximal Outerplanar Graph Drawings

    In this thesis, we study drawings of maximal outerplanar graphs that place vertices on integer coordinates. We introduce a new class of graphs, called umbrellas, and a new method of splitting maximal outerplanar graphs into systems of umbrellas. By doing so, we generate a new graph parameter, …

    waterloo Repository record for A 2-Approximation for the Height of Maximal Outerplanar Graph Drawings (opens in a new tab)

  2. Structure and properties of maximal outerplanar graphs.

    Outerplanar graphs are planar graphs that have a plane embedding in which each vertex lies on the boundary of the exterior region. An outerplanar graph is maximal outerplanar if the graph obtained by adding an edge is not outerplanar. Maximal outerplanar graphs are also known as triangulations of …

    louisville Repository record for Structure and properties of maximal outerplanar graphs. (opens in a new tab)

  3. Excluded-minor characterization of apex-outerplanar graphs

    It is well known that the class of outerplanar graphs is minor-closed and can be characterized by two excluded minors: K_4 and K_{2,3}. The class of graphs that contain a vertex whose removal leaves an outerplanar graph is also minor-closed. We provide the complete list of 57 excluded minors for …

    lsu-thes Repository record for Excluded-minor characterization of apex-outerplanar graphs (opens in a new tab)

  4. The Minimum Rank Problem for Outerplanar Graphs

    Given a simple graph G with vertex set V(G)={1,2,...,n} define S(G) to be the set of all real symmetric matrices A such that for all i not equal to j, the ijth entry of A is nonzero if and only if ij is in E(G). The range of the ranks of matrices in S(G) is of interest and can be determined by …

    byu Repository record for The Minimum Rank Problem for Outerplanar Graphs (opens in a new tab) Download PDF for The Minimum Rank Problem for Outerplanar Graphs (opens in a new tab)

  5. Explorations in Extremal Combinatorics: Graph Spectra, Codegree Squared Sum of Hypergraphs and Lin-Lu-Yau Ricci Curvature

    … a variety of extremal problems in spectral graph theory, hypergraph Tur\'an theory in the $\ell_2$-norm, and Lin-Lu-Yau Ricci curvature. We begin by studying the maximization of linear combinations of eigenvalues in relation to the adjacency matrix of a graph. For a graph $G$ on $n$ …

    south-carolina Repository record for Explorations in Extremal Combinatorics: Graph Spectra, Codegree Squared Sum of Hypergraphs and Lin-Lu-Yau Ricci Curvature (opens in a new tab)

  6. Connections to zero forcing: Tree covers and power domination

    <p>For a simple graph $G=(V,E),$ let $\mathcal{S}_+(G)$ denote the set of real positive semidefinite matrices $A=(a_{ij})$ such that $a_{ij}\neq 0$ if $\{i,j\}\in E$, $a_{ij}=0$ if $\{i,j\}\notin E$, and $a_{ii}$ is any real number. The maximum positive semidefinite nullity of $G$, denoted …

    iastate Repository record for Connections to zero forcing: Tree covers and power domination (opens in a new tab)

  7. Geometric Graph Theory and Wireless Sensor Networks

    … topology of the sensors is their visibility graph. Using a standard distributed algorithm, the sensors can build common knowledge of their network topology. We first study the following inverse visibility problem: What positions of sensors and obstacles define the computed visibility graph, …

    cuny-grad Repository record for Geometric Graph Theory and Wireless Sensor Networks (opens in a new tab)

  8. Minors of graphs of large path-width

    Let P be a graph with a vertex v such that P-v is a forest and let Q be an outerplanar graph. In 1993 Paul Seymour asked if every two-connected graph of sufficiently large path-width contains P or Q as a minor.mDefine g(H) as the minimum number for which there exists a positive integer p(H) such …

    gatech Repository record for Minors of graphs of large path-width (opens in a new tab)

  9. Simultaneous embedding and visualization of graphs

    Graph embedding and visualization problems arise in relational information visualization. The two primary goals in graph visualization are drawings that convey the relationships in the underlying data and drawings that are aesthetically pleasing. Often, we have a series of related graphs that we …

    arizona-thes Repository record for Simultaneous embedding and visualization of graphs (opens in a new tab)

  10. On K-trees and Special Classes of K-trees

    … the smallest k-tree is the k-clique. If G is a graph obtained by attaching a vertex v to a k-clique in a k-tree, then G is also a k-tree. Trees, connected acyclic graphs, are k-trees for k = 1. We introduce a new parameter known as the shell of a k-tree, and from the shell special subclasses of …

    mississippi Repository record for On K-trees and Special Classes of K-trees (opens in a new tab)

  11. Transforming Plane Triangulations by Simultaneous Diagonal Flips

    We explore the problem of transforming plane triangulations using simultaneous diagonal flips. Wagner showed that any n-vertex plane triangulation can be transformed to any other plane triangulation on equal number of vertices using a finite sequence of diagonal flips. Later on it has been …

    ottawa-retro Repository record for Transforming Plane Triangulations by Simultaneous Diagonal Flips (opens in a new tab)