Shifting attention from the plane to the sphere and torus, we extend the study of pseudo-triangulations. Planar representations of each surface are used. A number of theorems and concepts are taken from the plane and applied to the sphere and torus not only for pseudo-triangulations but for triangulations as well. We found the number of edges and faces in a triangulation on n vertices in the plane, on the sphere and on the torus.

Paper 1. This paper establishes several algebraic embedding theorems, each of which asserts that a certain kind of residuated structure can be embedded into a richer one. In almost all cases, the original structure has a compatible involution, which must be preserved by the embedding. The results, in conjunction with previous findings, yield separative axiomatizations of the deducibility relations of various substructural formal systems having double negation and contraposition axioms. The separation theorems go somewhat further than earlier ones in the literature, which either treated fewer subsignatures or focussed on the conservation of theorems only. Paper 2. It is proved that the variety of relevant disjunction lattices has the finite embeddability property (FEP). It follows that Avron’s relevance logic RMImin has a strong form of the finite model property, so it has a solvable deducibility problem. This strengthens Avron’s result that RMImin is decidable. Paper 3. An idempotent residuated po-monoid is semiconic if it is a subdirect product of algebras in which the monoid identity t is comparable with all other elements. It is proved that the quasivariety SCIP of all semiconic idempotent commutative residuated po-monoids is locally finite. The lattice-ordered members of this class form a variety SCIL, which is not locally finite, but it is proved that SCIL has the FEP. More generally, for every relative subvariety K of SCIP, the lattice-ordered members of K have the FEP. This gives a unified explanation of the strong finite model property for a range of logical systems. It is also proved that SCIL has continuously many semisimple subvarieties, and that the involutive algebras in SCIL are subdirect products of chains. Paper 4. Anderson and Belnap’s implicational system RMO can be extended conservatively by the usual axioms for fusion and for the Ackermann truth constant t. The resulting system RMO is algebraized by the quasivariety IP of all idempotent commutative residuated po-monoids. Thus, the axiomatic extensions of RMO are in one-to-one correspondence with the relative subvarieties of IP. It is proved here that a relative subvariety of IP consists of semiconic algebras if and only if it satisfies x (x t) x. Since the semiconic algebras in IP are locally finite, it follows that when an axiomatic extension of RMO has ((p t) p) p among its theorems, then it is locally tabular. In particular, such an extension is strongly decidable, provided that it is finitely axiomatized. / Thesis (Ph.D.)-University of KwaZulu-Natal, Westville, 2008.

We present a constant-factor approximation algorithm for computing an embedding of the shortest path metric of an unweighted graph into a tree, that minimizes the multiplicative distortion.

Thesis (Ph. D.)--University of Washington, 2001. / Vita. Includes bibliographical references (pages 42-44).

In this dissertation, we examine the nature of embeddings with regard to both combinatorial and geometric configurations. A combinatorial [r,k]-configuration is a collection of abstract points and sets (referred to as blocks) such that each point is a member of r blocks, each block is of size k, and these objects satisfy a linearity criterion: no two blocks intersect in more than one point. A geometric configuration requires that the points and blocks be realized as points and lines within the Euclidean plane. We provide improvements on the current bounds for the asymptotic existence of both combinatorial and geometric configurations. In addition, we examine the largely new problem of embedding configurations within larger configurations possessing regularity properties. Additionally, previously undiscovered geometric [r,k]-configurations are found as near-coverings of combinatorial configurations. / Graduate

Thesis (M.S.)--Worcester Polytechnic Institute. / Keywords: Embeddings; graph theory; pseudo-triangulations. Includes bibliographical references (leaves 30-31).

We present a constant-factor approximation algorithm for computing anembedding of the shortest path metric of an unweighted graph into atree, that minimizes the multiplicative distortion.

<p> Personalized PageRank with high teleportation probability enables exploring the environment of a seed. With this insight, one can use an orthogonal factorization of a set of personalized PageRank vectors, like SVD, to derive a 2-dimensional representation of the network. This can be done for the whole network or a smaller piece. The power of this method lies in the fact that only a few columns, compared to the size of the networks, can be used to generate a local representation of the part of the network we are interested in. This technique has the potential to be seamlessly used for higher order structures, such as hypergraphs which have found a great deal of use for real-world data. This work investigates the characteristics of personalized PageRank and how it compares to the transition probabilities on the graph in terms of their ability to develop low dimensional representations. A key focus of the thesis are the similarities between the embeddings generated due to PageRank and those generated by spectral methods.</p>

Sung Wing-wah. / Bibliography: leaves 42-45 / Thesis (M.Ph.)--Chinese University of Hong Kong, 1984

The central idea in this thesis is the introduction of a new isometric invariant of a Banach space. This is Property AI-I. A Banach space has Property AI-I if whenever a finite metric space almost-isometrically embeds into the space, it isometrically embeds. To study this property we introduce two further properties that can be thought of as finite metric variants of Dvoretzky's Theorem and Krivine's Theorem. We say that a Banach space satisfies the Finite Isometric Dvoretzky Property (FIDP) if it contains every finite subset of $\ell_2$ isometrically. We say that a Banach space has the Finite Isometric Krivine Property (FIKP) if whenever $\ell_p$ is finitely representable in the space then it contains every subset of $\ell_p$ isometrically. We show that every infinite-dimensional Banach space \emph{nearly} has FIDP and every Banach space nearly has FIKP. We then use convexity arguments to demonstrate that not every Banach space has FIKP, and thus we can exhibit classes of Banach spaces that fail to have Property AI-I. The methods used break down when one attempts to prove that there is a Banach space without FIDP and we conjecture that every infinite-dimensional Banach space has Property FIDP.