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