To see the other types of publications on this topic, follow the link: Planarität.
Dissertations / Theses on the topic 'Planarität'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 37 dissertations / theses for your research on the topic 'Planarität.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Zschalig, Christian. "Characterizations of Planar Lattices by Left-relations." Doctoral thesis, Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2009. http://nbn-resolving.de/urn:nbn:de:bsz:14-ds-1240834941828-67021.
Full textAbstract:
Recently, Formal Concept Analysis has proven to be an efficient method for the analysis and representation of information. However, the possibility to visualize concept hierarchies is being affected by the difficulty of drawing attractive diagrams automatically. Reducing the number of edge crossings seems to increase the readability of those drawings. This dissertation concerns with a mandatory prerequisite of this constraint, namely the characterization and visual representation of planar lattices. The manifold existing approaches and algorithms are thereby considered under a different point of view. It is well known that exactly the planar lattices (or planar posets) possess an additional order ``from left to right''. Our aim in this work is to define left-relations and left-orders more precisely and to describe several aspects of planar lattices with their help. The three approaches employed structure the work in as many parts: Left-relations on lattices allow a more efficient consideration of conjugate orders since they are uniquely determined by the sorting of the meet-irreducibles. Additionally, the restriction on the meet-irreducibles enables us to achieve an intuitive description of standard contexts of planar lattices similar to the consecutive-one property. With the help of left-relations on diagrams, planar lattices can indeed be drawn without edge crossings in the plane. Thereby, lattice-theoretically found left-orders can be detected in the graphical representation again. Furthermore, we modify the left-right-numbering algorithm in order to obtain attribute-additive and plane drawings of planar lattices. Finally, we will consider left-relations on contexts. They turn out to be fairly similar structures to the Ferrers-graphs. Planar lattices can be characterized by a property of these graphs, namely the bipartiteness. We will constructively prove this result. Subsequently, we can design an efficient algorithm that finds all non-similar plane diagrams of a latticeDie Formale Begriffsanalyse hat sich in den letzten Jahren als effizientes Werkzeug zur Datenanalyse und -repräsentation bewährt. Die Möglichkeit der visuellen Darstellung von Begriffshierarchien wird allerdings durch die Schwierigkeit, ansprechende Diagramme automatisch generieren zu können, beeinträchtigt. Offenbar sind Diagramme mit möglichst wenig Kantenkreuzungen für den menschlichen Anwender leichter lesbar. Diese Arbeit beschäftigt sich mit mit einer diesem Kriterium zugrunde liegenden Vorleistung, nämlich der Charakterisierung und Darstellung planarer Verbände. Die schon existierenden vielfältigen Ansätze und Methoden werden dabei unter einem neuen Gesichtspunkt betrachtet. Bekannterweise besitzen genau die planaren Verbände (bzw. planare geordnete Mengen) eine zusätzliche Ordnung "von links nach rechts". Unser Ziel in dieser Arbeit ist es, solche Links-Relationen bzw. Links-Ordnungen genauer zu definieren und verschiedene Aspekte planarer Verbände mit ihrer Hilfe zu beschreiben. Die insgesamt drei auftretenden Sichtweisen gliedern die Arbeit in ebensoviele Teile: Links-Relationen auf Verbänden erlauben eine effizientere Behandlung konjugierter Ordnungen, da sie durch die Anordnung der Schnitt-Irreduziblen schon eindeutig festgelegt sind. Außerdem erlaubt die Beschränkung auf die Schnitt-Irreduziblen eine anschauliche Beschreibung von Standardkontexten planarer Verbände ähnlich der consecutive-one property. Mit Hilfe der Links-Relationen auf Diagrammen können planare Verbände tatsächlich eben gezeichnet werden. Dabei lassen sich verbandstheoretisch ermittelte Links-Ordnungen in der graphischen Darstellung wieder finden. Weiterhin geben wir in eine Modifikation des left-right-numbering an, mit der planare Verbände merkmaladditiv und eben gezeichnet werden können. Schließlich werden wir Links-Relationen auf Kontexten betrachten. Diese stellen sich als sehr ähnlich zu Ferrers-Graphen heraus. Planare Verbände lassen sich durch eine Eigenschaft dieser Graphen, nämlich die Bipartitheit, charakterisieren. Wir werden dieses Ergebnis konstruktiv beweisen und darauf aufbauend einen effizienten Algorithmus angeben, mit dem alle nicht-ähnlichen ebenen Diagramme eines Verbandes bestimmt werden können
2
Zschalig, Christian. "Characterizations of Planar Lattices by Left-relations." Doctoral thesis, Technische Universität Dresden, 2008. https://tud.qucosa.de/id/qucosa%3A23687.
Full textAbstract:
Recently, Formal Concept Analysis has proven to be an efficient method for the analysis and representation of information. However, the possibility to visualize concept hierarchies is being affected by the difficulty of drawing attractive diagrams automatically. Reducing the number of edge crossings seems to increase the readability of those drawings. This dissertation concerns with a mandatory prerequisite of this constraint, namely the characterization and visual representation of planar lattices. The manifold existing approaches and algorithms are thereby considered under a different point of view. It is well known that exactly the planar lattices (or planar posets) possess an additional order ``from left to right''. Our aim in this work is to define left-relations and left-orders more precisely and to describe several aspects of planar lattices with their help. The three approaches employed structure the work in as many parts: Left-relations on lattices allow a more efficient consideration of conjugate orders since they are uniquely determined by the sorting of the meet-irreducibles. Additionally, the restriction on the meet-irreducibles enables us to achieve an intuitive description of standard contexts of planar lattices similar to the consecutive-one property. With the help of left-relations on diagrams, planar lattices can indeed be drawn without edge crossings in the plane. Thereby, lattice-theoretically found left-orders can be detected in the graphical representation again. Furthermore, we modify the left-right-numbering algorithm in order to obtain attribute-additive and plane drawings of planar lattices. Finally, we will consider left-relations on contexts. They turn out to be fairly similar structures to the Ferrers-graphs. Planar lattices can be characterized by a property of these graphs, namely the bipartiteness. We will constructively prove this result. Subsequently, we can design an efficient algorithm that finds all non-similar plane diagrams of a lattice.Die Formale Begriffsanalyse hat sich in den letzten Jahren als effizientes Werkzeug zur Datenanalyse und -repräsentation bewährt. Die Möglichkeit der visuellen Darstellung von Begriffshierarchien wird allerdings durch die Schwierigkeit, ansprechende Diagramme automatisch generieren zu können, beeinträchtigt. Offenbar sind Diagramme mit möglichst wenig Kantenkreuzungen für den menschlichen Anwender leichter lesbar. Diese Arbeit beschäftigt sich mit mit einer diesem Kriterium zugrunde liegenden Vorleistung, nämlich der Charakterisierung und Darstellung planarer Verbände. Die schon existierenden vielfältigen Ansätze und Methoden werden dabei unter einem neuen Gesichtspunkt betrachtet. Bekannterweise besitzen genau die planaren Verbände (bzw. planare geordnete Mengen) eine zusätzliche Ordnung "von links nach rechts". Unser Ziel in dieser Arbeit ist es, solche Links-Relationen bzw. Links-Ordnungen genauer zu definieren und verschiedene Aspekte planarer Verbände mit ihrer Hilfe zu beschreiben. Die insgesamt drei auftretenden Sichtweisen gliedern die Arbeit in ebensoviele Teile: Links-Relationen auf Verbänden erlauben eine effizientere Behandlung konjugierter Ordnungen, da sie durch die Anordnung der Schnitt-Irreduziblen schon eindeutig festgelegt sind. Außerdem erlaubt die Beschränkung auf die Schnitt-Irreduziblen eine anschauliche Beschreibung von Standardkontexten planarer Verbände ähnlich der consecutive-one property. Mit Hilfe der Links-Relationen auf Diagrammen können planare Verbände tatsächlich eben gezeichnet werden. Dabei lassen sich verbandstheoretisch ermittelte Links-Ordnungen in der graphischen Darstellung wieder finden. Weiterhin geben wir in eine Modifikation des left-right-numbering an, mit der planare Verbände merkmaladditiv und eben gezeichnet werden können. Schließlich werden wir Links-Relationen auf Kontexten betrachten. Diese stellen sich als sehr ähnlich zu Ferrers-Graphen heraus. Planare Verbände lassen sich durch eine Eigenschaft dieser Graphen, nämlich die Bipartitheit, charakterisieren. Wir werden dieses Ergebnis konstruktiv beweisen und darauf aufbauend einen effizienten Algorithmus angeben, mit dem alle nicht-ähnlichen ebenen Diagramme eines Verbandes bestimmt werden können.
3
Fowler, Joe. "Unlabled Level Planarity." Diss., The University of Arizona, 2009. http://hdl.handle.net/10150/195812.
Full textAbstract:
Consider a graph G with vertex set V in which each of the n vertices is assigned a number from the set {1, ..., k} for some positive integer k. This assignment phi is a labeling if all k numbers are used. If phi does not assign adjacent vertices the same label, then phi partitions V into k levels. In a level drawing, the y-coordinate of each vertex matches its label and the edges are drawn strictly y-monotone. This leads to level drawings in the xy-plane where all vertices with label j lie along the line lj = {(x, j) : x in Reals} and where each edge crosses any of the k horizontal lines lj for j in [1..k] at most once. A graph with such a labeling forms a level graph and is level planar if it has a level drawing without crossings.We first consider the class of level trees that are level planar regardless of their labeling. We call such trees unlabeled level planar (ULP). We describe which trees are ULP and provide linear-time level planar drawing algorithms for any labeling. We characterize ULP trees in terms of two forbidden subdivisions so that any other tree must contain a subtree homeomorphic to one of these. We also provide linear-time recognition algorithms for ULP trees. We then extend this characterization to all ULP graphs with five additional forbidden subdivisions, and provide linear-time recogntion and drawing algorithms for any given labeling.
4
Hayer, Matthias. "Testing planarity in linear time." Thesis, Georgia Institute of Technology, 1994. http://hdl.handle.net/1853/30483.
Full text
5
Bachmaier, Christian. "Circle planarity of level graphs." [S.l.] : [s.n.], 2004. http://deposit.ddb.de/cgi-bin/dokserv?idn=973953985.
Full text
6
Estrella, Balderrama Alejandro. "Simultaneous Embedding and Level Planarity." Diss., The University of Arizona, 2009. http://hdl.handle.net/10150/195738.
Full textAbstract:
Graphs are a common model for representing information consisting of a set of objects or entities and a set of connections or relations between them. Graph Drawing is concerned with the automatic visualization of graphs in order to make the information useful. That is, a good drawing should be helpful in the application domain where it is used by capturing the relationships in the underlying data. We consider two important problems in automated graph drawing: simultaneous embedding and level planarity. Simultaneous embedding is the problem of drawing multiple graphs while maintaining the readability of each graph independently and preserving the mental map when going from one graph to another. In this case, each graph has the same vertex set (same entities) but different edge sets (different relationships). Level planarity arises in the layout of graphs that contain hierarchical relationships. When drawing graphs in the plane, this translates to a restricted form of planarity where the vertical order of the entities is pre-determined. We consider the computational complexity of the simultaneous embedding problem. In particular, we show that in its generality the simultaneous embedding problem is NP-hard if the edges are drawn as straight-lines. We present algorithms for drawing graphs on predetermined levels, which allow the simultaneous embedding of restricted types of graphs, such as outerplanar graphs, trees and paths. Finally, our practical contribution is a tool that implements known and novel algorithms related to simultaneous embedding and level planarity and can be used both as a visualization software and as an aid to study theoretical problems.
7
Taylor, Martyn G. "Planarity testing by path addition." Thesis, University of Kent, 2011. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.580367.
Full textAbstract:
The first linear-time planarity testing algorithm was developed in 1974 by Hopcroft and Tarjan (H&T) [32] using a method to split a biconnected graph up into edge disjoint paths and then sequentially embed them to test for planarity (a path addition method). Shortly afterwards Booth and Leuker [5] developed an alternative vertex addition linear-time planarity test, based on the earlier work of Lempel, Evan and Cederbaum [47], using a new PQ-Tree data structure. Since then there have been many developments in PQ- Tree vertex addition (and related PC-Tree edge addition) methods including authors such as: Chiba et al. [14]; Shih & Hsu [35, 69]; Boyer and Myrvold [10, 11]; and Haeupler and Tarjan [29]. In comparison, path addition has changed very little from the original algorithm. In 1984, Williamson [84] showed how H&T's algorithm can be extended to find Kuratowski sub-graphs in the event of a non-planar graph; and, in 1993, Mehlhorn, Mutzel and Naher [53] produced an implementation (in C) of H&T's algorithm and extended it to create a planar embedding of a graph. This has remained the state-of-the-art in path addition algorithms for over a decade. Recently", de Fraysseix formulated an algorithm [15, 17], based on Tremaux Trees and a characterisation of planarity by W. Wu [87]; this may prove to be a highly optimised version of H&T's algorithm but is difficult to definitively prove as only an outline of its planarity testing phase is provided. These authors represent the majority of the work on path addition methods of planarity testing and embedding; indicating that it receives little attention compared to vertex or edge addition methods This thesis attempts to reinvigorate the field of path addition and demonstrates: • How Trernaux Trees, which allow undirected connected graphs to be represented as a simple partial order relationship are fundamentally related to H&T-‘^planarity testing algorithm and includes some related invariant properties of these trees; • That the restriction on H&T's planarity testing algorithm to test undirected biconnected graphs can be relaxed to undirected connected graphs; • How to generate all possible embeddings of a biconnected component and how to extend this to generate all possible embeddings of separable graphs; and • Empirical Testing of various graph types and sizes to validate these results.
8
Tassion, Vincent. "Planarité et Localité en Percolation." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2014. http://tel.archives-ouvertes.fr/tel-01061007.
Full textAbstract:
Cette thèse s'inscrit dans l'étude mathématique de la percolation, qui regroupe une famille de modèles présentant une transition de phase. Des avancées majeures au cours des quinze dernières années, notamment l'invention du SLE et la preuve de l'invariance conforme de la percolation de Bernoulli critique, nous permettent aujourd'hui d'avoir une image très complète de la percolation de Bernoulli sur le réseau triangulaire. Cependant, de nombreuses questions demeurent ouvertes, et ont motivé notre travail.La première d'entre elle est l'universalité de la percolation plane, qui affirme que les propriétés macroscopiques de la percolation plane critique ne devraient pas dépendre du réseau sous-jacent à sa définition. Nous montrons, dans le cadre de la percolation Divide and Color, un résultat qui va dans le sens de cette universalité et identifions, dans ce contexte, des phénomènes macroscopiques indépendants du réseau microscopique. Une version plus faible d'universalité est donnée par la théorie de Russo-Seymour-Welsh (RSW), et sa validité est connue pour la percolation de Bernoulli (sans dépendance) sur les réseaux plans suffisamment symétriques. Nous étudions de nouveaux arguments de type RSW pour des modèles de percolation avec dépendance. La deuxième question que nous avons abordée est celle de l'absence d'une composante connexe ouverte infinie au point critique, une question importante du point de vue physique, puisqu'elle traduit la continuité de la transition de phase. Dans deux travaux en collaboration avec Hugo Duminil-Copin et Vladas Sidoravicius, nous montrons que la transition de phase est continue pour la percolation de Bernoulli sur le graphe Z^2x{0,...,k}, et pour la percolation FK sur le réseau carré avec paramètre q inférieur ou égal à 4. Enfin, la dernière question qui nous a guidés est la localité du point critique : la donnée des boules de grands rayons d'un graphe suffit-elle à identifier avec une bonne précision la valeur du point critique? Dans un travail en collaboration avec Sébastien Martineau, nous répondons de manière affirmative à cette question dans le cadre des graphes de Cayley de groupes abéliens.
9
Klein, Philip N. (Philip Nathan). "An efficient parallel algorithm for planarity." Thesis, Massachusetts Institute of Technology, 1986. http://hdl.handle.net/1721.1/34303.
Full textAbstract:
Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1986.MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING
Bibliography: leaves 56-57.
by Philip Nathan Klein.
M.S.
10
Heinz, Adrian. "Planarity testing and drawing in Jedit 4.0." Virtual Press, 2001. http://liblink.bsu.edu/uhtbin/catkey/1204201.
Full textAbstract:
In this project, an enhanced version of Jedit is presented. Jedit is a Graph Editor developed at Ball State University by a group of students under the direction of Dr. Jay Bagga. The following paper describes the new version, named Jedit 4.0.In this version two new algorithms are implemented. These are: Planarity Testing and Planarity Drawing. The first algorithm tests a graph for planarity and the second one makes a planar embedding of the graph in a grid of size (n-2) x (n-2), where n is the order of the graph. Planar graphs have important applications in the fields of computer engineering, architecture, and many others.Jedit 4.0 also includes new features that were not available in earlier versions. The new features include: graph rotation operation, graph complement, drawing of well-known graphs, and credits window. Several modifications and additions to existing features and algorithms have also been carried out.Jedit 4.0 uses swing java technology what provides a more elegant look. Drop down menus have also been added to provide the user an easier way to use Jedit.Department of Computer Science
11
Zeranski, Robert [Verfasser]. "Satisfiability Characterizations of Upward Planarity Problems / Robert Zeranski." München : Verlag Dr. Hut, 2014. http://d-nb.info/105155053X/34.
Full text
12
Nowlin, Jeffrey L. "Planarity in ROMDD's of multiple-valued symmetric functions." Thesis, Monterey, Calif. : Springfield, Va. : Naval Postgraduate School ; Available from National Technical Information Service, 1996. http://handle.dtic.mil/100.2/ADA309273.
Full textAbstract:
Thesis (M.S. in Electrical Engineering) Naval Postgraduate School, March 1996.Thesis advisor(s): Jon T. Butler. "March 1996." Bibliography: p. 51. Also available online. Mode of access: World Wide Web.
13
Borradaile, Glencora. "Exploiting planarity for network flow and connectivity problems." View abstract/electronic edition; access limited to Brown University users, 2008. http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:3318294.
Full text
14
Chan, Hubert. "A Parameterized Algorithm for Upward Planarity Testing of Biconnected Graphs." Thesis, University of Waterloo, 2003. http://hdl.handle.net/10012/1090.
Full textAbstract:
We can visualize a graph by producing a geometric representation of the graph in which each node is represented by a single point on the plane, and each edge is represented by a curve that connects its two endpoints.
Directed graphs are often used to model hierarchical structures; in order to visualize the hierarchy represented by such a graph, it is desirable that a drawing of the graph reflects this hierarchy. This can be achieved by drawing all the edges in the graph such that they all point in an upwards direction. A graph that has a drawing in which all edges point in an upwards direction and in which no edges cross is known as an upward planar graph. Unfortunately, testing if a graph is upward planar is NP-complete.
Parameterized complexity is a technique used to find efficient algorithms for hard problems, and in particular, NP-complete problems. The main idea is that the complexity of an algorithm can be constrained, for the most part, to a parameter that describes some aspect of the problem. If the parameter is fixed, the algorithm will run in polynomial time.
In this thesis, we investigate contracting an edge in an upward planar graph that has a specified embedding, and show that we can determine whether or not the resulting embedding is upward planar given the orientation of the clockwise and counterclockwise neighbours of the given edge. Using this result, we then show that under certain conditions, we can join two upward planar graphs at a vertex and obtain a new upward planar graph. These two results expand on work done by Hutton and Lubiw.
Finally, we show that a biconnected graph has at most k!8k-1 planar embeddings, where k is the number of triconnected components. By using an algorithm by Bertolazzi et al. that tests whether a given embedding is upward planar, we obtain a parameterized algorithm, where the parameter is the number of triconnected components, for testing the upward planarity of a biconnected graph. This algorithm runs in O(k!8kn3) time.
15
Brückner, Guido [Verfasser], and D. [Akademischer Betreuer] Wagner. "Planarity Variants for Directed Graphs / Guido Brückner ; Betreuer: D. Wagner." Karlsruhe : KIT-Bibliothek, 2021. http://d-nb.info/1238148018/34.
Full text
16
Barbanchon, Régis. "Réductions fines entre problèmes NP-complets : linéarité, planarité, parcimonie, et minimalité logique." Caen, 2003. http://www.theses.fr/2003CAEN2066.
Full textAbstract:
Nous étudions les problèmes combinatoires NP-complets autour de la Satisfaisabilité (SAT) : 3-Colorabilité (3COL), Hamiltonicité (HAM), etc. , et les réductions fines entre ces problèmes et leurs versions planaires. Nous cherchons à préserver la structure des solutions (parcimonie), la complexité des problèmes (linéarité), et la géométrie des instances (planarité). Nous exhibons une réduction quadratique et parcimonieuse de 3COL à PLAN-3COL et une réduction linéaire, planaire, et parcimonieuse de SAT à 3COL, unifiant et rafinant les preuves de NP-complétude et de \#P-complétude pour 3COL, PLAN-3COL, \#3COL et \#PLAN-3COL, et montrant la DP-complétude de UNIQUE-3COL et UNIQUE-PLAN-3COL. Nous établissons l'équivalence linéaire et parcimonieuse de PLAN-SAT et de PLAN-HAM, un lien peu probable entre SAT et HAM. Nous exhibons enfin une formule Existentielle Monadique du Second Ordre prouvée minimale et unique, définissant un problème NP-complet sur structures bijectives.
17
Noschinski, Lars Verfasser], Tobias [Akademischer Betreuer] [Gutachter] [Nipkow, and Kurt [Gutachter] Mehlhorn. "Formalizing Graph Theory and Planarity Certificates / Lars Noschinski. Betreuer: Tobias Nipkow. Gutachter: Kurt Mehlhorn ; Tobias Nipkow." München : Universitätsbibliothek der TU München, 2016. http://d-nb.info/1104933624/34.
Full text
18
Bläsius, Thomas [Verfasser], and D. [Akademischer Betreuer] Wagner. "New Approaches to Classic Graph-Embedding Problems - Orthogonal Drawings & Constrained Planarity / Thomas Bläsius. Betreuer: D. Wagner." Karlsruhe : KIT-Bibliothek, 2015. http://d-nb.info/1075809401/34.
Full text
19
Rutter, Ignaz [Verfasser], and D. [Akademischer Betreuer] Wagner. "The many faces of planarity : matching, augmentation, and embedding algorithms for planar graphs / Ignaz Rutter. Betreuer: D. Wagner." Karlsruhe : KIT-Bibliothek, 2011. http://d-nb.info/1015557848/34.
Full text
20
Bhandari, Yuba R. "Pressure Induced Structural Changes and Gas Diffusion Pathways in Monomeric Fluorescent Proteins." FIU Digital Commons, 2013. http://digitalcommons.fiu.edu/etd/886.
Full textAbstract:
Fluorescent proteins (FPs) are extremely valuable biochemical markers which have found a wide range of applications in cellular and molecular biology research. The monomeric variants of red fluorescent proteins (RFPs), known as mFruits, have been especially valuable for in vivo applications in mammalian cell imaging. Fluorescent proteins consist of a chromophore caged in the beta-barrel protein scaffold. The photophysical properties of an FP is determined by its chromophore structure and its interactions with the protein barrel.
Application of hydrostatic pressure on FPs results in the modification of the chromophore environment which allows a systematic study of the role of the protein-chromophore interactions on photophysical properties of FPs. Using Molecular Dynamics (MD) computer simulations, I investigated the pressure induced structural changes in the monomeric variants mCherry, mStrawberry, and Citrine. The results explain the molecular basis for experimentally observed pressure responses among FP variants. It is found that the barrel flexibility, hydrogen bonding interactions and chromophore planarity of the FPs can be correlated to their contrasting photophysical properties at vaious pressures.
I also investigated the oxygen diffusion pathways in mOrange and mOrange2 which exhibit marked differences in oxygen sensitivities as well as photostability. Such computational identifications of structural changes and oxygen diffusion pathways are important in guiding mutagenesis efforts to design fluorescent proteins with improved photophysical properties.
21
Singh, Mandeep. "STUDIES ON THE SIZE AND NON-PLANARITY OF AROMATIC STACKING MOIETY ON CONFORMATION SELECTIVITY AND THERMAL STABILIZATION OF G-QUADRUPLEXES." Scholarly Commons, 2020. https://scholarlycommons.pacific.edu/uop_etds/3725.
Full textAbstract:
Targeting DNA has the advantage over proteins for cancer remediation because of the fewer copies of the ligands required for the desired therapeutic effect. Traditionally, covalent DNA binders like alkylating agents have been used to induce genetic instability through the formation of DNA lesions and strand breaks, leading to cellular apoptosis. The primary drawback of this treatment is the non-specific binding that affects both cancerous and non-cancerous cells. G-quadruplexes are the DNA secondary structures that are present in abundance near the promoter regions of the oncogenes and are involved in the regulation of their activities. A ligand-mediated stabilization of G-quadruplexes in the promoter regions and down-regulation of the associated oncogenes have been validated. In contrast to alkylating agents, G-quadruplex ligands induce genetic stabilization through non-covalent interactions. They can be designed to interact specifically with G-quadruplex DNA over duplex DNA, which reduce side effects arising from the off-targeting. G-quadruplex ligands invariably have the large planar aromatic moiety to interact with G-quadruplexes through π- π stacking interactions. For determining the size effect of the aromatic moiety on stabilization of G-quadruplexes, a series of ligands were synthesized by conjugating nucleobases or 1,10-phenanthroline with an aminoglycoside, neomycin. The resulting conjugates increased the binding affinity synergistically and enabled us to study the effect of the stacking moiety required for G-quadruplex stabilization. Nucleobase-neomycin conjugates did not show stabilization stabilize of human telomeric G-quadruplex. 1,10-Phenanthroline-neomycin conjugate (7b) on the other hand binds to human telomeric G-quadruplex with a Ka of (8.92.4)×108 M-1 and inhibits telomerase activity at 1.56 µM probably through G-quadruplex stabilization. Moving forward, we further enlarged the aromatic moiety by tethering two 1,10-phenantholine molecules together through a five-atom linker. The resulting molecule (2-Clip-phen) was conjugated with various amino-containing side chains. 2-Clip-phen derivatives showed at least 30 times weaker binding to duplex DNA over G-quadruplex DNA. In addition, compounds showed a preference for the antiparallel G-quadruplex conformation over parallel and hybrid G-quadruplex conformations, as shown in the CD spectroscopy studies. Ligands 11 and 13 induced the formation of an antiparallel G-quadruplex from random coils and stabilize it to 60 oC (Tm) in a salt-free condition. Mass spectrometry study showed the formation of a two-tetrad G-quadruplex with the 2-Clip-phen ligand. Docking study showed that the ligand interacts most favorably with antiparallel G-quadruplex conformation, which is supported further by the larger thermal stabilization effect on antiparallel G-quadruplex compared with other G-quadruplex conformations. Our study suggests that 2-Clip-phen can be used as a scaffold for designing G-quadruplex binding ligands that preferentially bind to antiparallel G-quadruplexes, which has never been reported before.
22
Coelho, Vinícius de Sousa. "Um estudo aplicado de paralelismo para o problema do subgrafo planar de peso máximo." Universidade Federal de Goiás, 2018. http://repositorio.bc.ufg.br/tede/handle/tede/8503.
Full textAbstract:
Submitted by Liliane Ferreira (ljuvencia30@gmail.com) on 2018-05-21T15:48:27Z
No. of bitstreams: 2
Dissertação - Vinícius de Sousa Coelho - 2018.pdf: 1071318 bytes, checksum: fba98fd6feb916f0400af915d4d92a2b (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2018-05-22T12:14:46Z (GMT) No. of bitstreams: 2 Dissertação - Vinícius de Sousa Coelho - 2018.pdf: 1071318 bytes, checksum: fba98fd6feb916f0400af915d4d92a2b (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Made available in DSpace on 2018-05-22T12:14:46Z (GMT). No. of bitstreams: 2 Dissertação - Vinícius de Sousa Coelho - 2018.pdf: 1071318 bytes, checksum: fba98fd6feb916f0400af915d4d92a2b (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2018-04-27
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES
The Maximum Weight Planar Subgraph Problem (MWPSP) consists of identifying a planar subgraph of maximum weight of a given edge-weighted graph. This work proposes new heuristic solutions, mainly using Graphic Processing Units, based on local transformations on the graph topology, consisting of vertex and edge insertion/relocation moves. Sequential and parallel implementations were built and applied to various numerical instances with promising results. One of the approaches requires only 25 seconds of execution, being more than 200 times faster than its corresponding sequential version, for a 100-vertex instance. In terms of quality, the proposed solutions obtained better results than state of the art proposals.
O problema do subgrafo planar de peso máximo (MWPSP) consiste em extrair um subgrafo planar maximal, a partir de um grafo completo com pesos atribuídos às arestas, cuja soma dos pesos das arestas seja máxima. Este trabalho propõe soluções heurísticas, construídas por meio de Unidades de Processamento Gráfico (GPUs), baseadas em transformações locais na topologia do grafo através da inserção/realocação de vértices e arestas. Implementações sequencias e paralelas foram propostas, apresentando resultados satisfatórios. Em uma das propostas, a versão paralela requer cerca de 25 segundos de execução em uma instância de 100 vértices, sendo cerca de 200 vezes mais rápida que a versão sequencial correspondente. Em termos de qualidade da solução, as propostas superaram os resultados obtidos por algoritmos no estado da arte.
23
Streib, Noah Sametz. "Planar and hamiltonian cover graphs." Diss., Georgia Institute of Technology, 2011. http://hdl.handle.net/1853/43744.
Full textAbstract:
This dissertation has two principal components: the dimension of posets with planar cover graphs, and the cartesian product of posets whose cover graphs have hamiltonian cycles that parse into symmetric chains. Posets of height two can have arbitrarily large dimension. In 1981, Kelly provided an infinite sequence of planar posets that shows that the dimension of planar posets can also be arbitrarily large. However, the height of the posets in this sequence increases with the dimension. In 2009, Felsner, Li, and Trotter conjectured that for each integer h at least 2, there exists a least positive integer c(h) so that if P is a poset with a planar cover graph (the class of posets with planar cover graphs includes the class of planar posets) and the height of P is h, then the dimension of P is at most c(h). In the first principal component of this dissertation we prove this conjecture. We also give the best known lower bound for c(h), noting that this lower bound is far from the upper bound. In the second principal component, we consider posets with the Hamiltonian Cycle--Symmetric Chain Partition (HC-SCP) property. A poset of width w has this property if its cover graph has a hamiltonian cycle which parses into w symmetric chains. This definition is motivated by a proof of Sperner's theorem that uses symmetric chains, and was intended as a possible method of attack on the Middle Two Levels Conjecture. We show that the subset lattices have the HC-SCP property by showing that the class of posets with the strong HC-SCP property, a slight strengthening of the HC-SCP property, is closed under cartesian product with a two-element chain. Furthermore, we show that the cartesian product of any two posets from this strong class has the (weak) HC-SCP property.
24
Dehdari, Jonathan M. "Crossing Dependencies in Persian." Diss., CLICK HERE for online access, 2006. http://contentdm.lib.byu.edu/ETD/image/etd1441.pdf.
Full text
25
Rasmussen, Danne Rene, and danne@optusnet com au. "A Theoretical Approach to Molecular Design: Planar-Tetracoordinate Carbon." The Australian National University. Research School of Chemistry, 2000. http://thesis.anu.edu.au./public/adt-ANU20010702.115616.
Full textAbstract:
A number of novel hydrocarbon cage systems have been designed and characterized using ab initio molecular orbital calculations at the MP2 and B3-LYP levels. In particular,equilibrium structures for five families of molecules, hemialkaplanes, hemispiroalkaplanes, alkaplanes, spiroalkaplanes and dimethanospiroalkaplanes, have been examined in detail with the aim of designing a saturated hydrocarbon with a planar-tetracoordinate carbon atom and with a view to identifying appropriate synthetic targets.
¶
The hemialkaplanes and hemispiroalkaplanes are constructed from a spiropentane or neopentane subunit, respectively, which is capped by a cyclic hydrocarbon. The hemispiroalkaplanes are predicted to contain a pyramidal-tetracoordinate carbon atom possessing a lone pair of electrons. Protonation at this apical carbon atom is found to be highly favorable, resulting in a remarkably high basicity for a saturated hydrocarbon. The proton affinities of the hemispiroalkaplanes are calculated to be more than 1170 kJ mol[superscript -1] , even greater than those for the diamine "proton sponges".
¶
The alkaplanes and the spiroalkaplanes, which are constructed by bicapping a neopentane or spiropentane subunit, respectively, with a pair of cyclic hydrocarbons, show unprecedented flattening of a tetracoordinate carbon atom. Linking the spiroalkaplane caps with methano bridges gives the dimethanospiroalkaplanes, two of which, dimethanospirooctaplane and dimethanospirobinonaplane, achieve exact planarity at the central carbon atom. They are the first neutral saturated hydrocarbons predicted to contain an exactly planartetracoordinate carbon atom. This has been achieved through structural constraints alone. The electronic structure at the central carbon atom results in a highest occupied molecular orbital corresponding to a p-type lone pair. Consequently, the adiabatic ionization energies for octaplane, spirooctaplane and dimethanospirooctaplane (approximately 5 eV) are predicted to be similar to those of lithium and sodium - incredibly low for a saturated hydrocarbon.
¶
Some consideration has been given to likely pathways for unimolecular decomposition for all species. Predicted structures, heats of formation and strain energies for all the novel hydrocarbons are also detailed. Tetramethylhemispirooctaplane and dimethanospirobinonaplane are identified as the preferred synthetic targets.
26
Luo, Ying. "SLURRY CHEMISTRY EFFECTS ON COPPER CHEMICAL MECHANICAL PLANARIZATION." Master's thesis, University of Central Florida, 2004. http://digital.library.ucf.edu/cdm/ref/collection/ETD/id/4470.
Full textAbstract:
Chemical-mechanical Planarization (CMP) has emerged as one of the fastest-growing processes in the semiconductor manufacturing industry, and it is expected to show equally explosive growth in the future (Braun, 2001). The development of CMP has been fueled by the introduction of copper interconnects in microelectronic devices. Other novel applications of CMP include the fabrications of microelectromechanical systems (MEMS), advanced displays, three dimensional systems, and so on (Evans, 2002). CMP is expected to play a key role in the next-generation micro- and nanofabrication technologies (Singh, et al., 2002). Despite the rapid increase in CMP applications, the fundamental understanding of the CMP process has been lacking, particularly the understanding of the wafer-slurry-pad interactions that occur during the CMP process. Novel applications of CMP are expected to expand to materials that are complex chemically and fragile mechanically. Thus, fundamental understanding and improvement of slurry design for CMP is the key to the development of sophisticated next-generation CMP processes. Slurry performance for CMP can be determined by several output parameters including removal rate, global planarity, surface topography, and surface defectivity. To achieve global planarity, it is essential to form a very thin passivating surface layer (<2 nm) that is subsequently removed by the mechanical component of the slurry (Kaufman et al., 1991) or by combined chemo-mechanical effects (Tamboli, 2000). Chemical additives like hydrogen peroxide (H?O?), potassium ferricyanide, and ferric chloride are added to slurries as oxidizers in order to form a desirable surface layer. Other chemical additives such as inhibitors (e.g. benzotriazole) and complexing agents (e.g. ammonia) are added to the copper slurry in order to modify the oxide layer. That the removal rate of the thin surface layer is greater at the highest regions of the wafer surface than at the lowest regions leads to surface planarity. In this study, various complexing agents and inhibitors are combined to form slurry chemistry for copper CMP processing in H?O? based slurries at pH values ranging from 2 to 10. Two complexing agents (glycine and Ethylenediamine) and one inhibitor (3-amino-1, 2, 4-triazole) were selected as slurry constituents for detailed chemical synergistic effect study because they showed good materials removal and surface planarity performances. To understand the fundamental mechanisms involved in copper CMP process with the afore-mentioned slurry chemical formations, various techniques, such as electrochemical testing techniques (including potentiodynamic polarization and electrochemical impedance spectroscopy), x-ray photoelectron spectroscopy (XPS), atomic force microscopy (AFM), and scanning electron microscopy (SEM), were applied. As a result, guidelines for optimized slurry chemical formulation were arrived at and the possible mechanisms of surface-chemical-abrasive interactions were determined. From applications point of view, this study serves as a guide for further investigations in pursuing highly effective slurry formulations for copper/low-k interconnect applications.M.S.
Department of Mechanical, Materials and Aerospace Engineering;
Engineering and Computer Science
Mechanical, Materials and Aerospace Engineering;
27
Belhedi, Amira. "Modélisation du bruit et étalonnage de la mesure de profondeur des caméras Temps-de-Vol." Thesis, Clermont-Ferrand 1, 2013. http://www.theses.fr/2013CLF1MM08/document.
Full textAbstract:
Avec l'apparition récente des caméras 3D, des perspectives nouvelles pour différentes applications de l'interprétation de scène se sont ouvertes. Cependant, ces caméras ont des limites qui affectent la précision de leurs mesures. En particulier pour les caméras Temps-de-Vol, deux types d'erreur peuvent être distingués : le bruit statistique de la caméra et la distorsion de la mesure de profondeur. Dans les travaux de la littérature des caméras Temps-de-Vol, le bruit est peu étudié et les modèles de distorsion de la mesure de profondeur sont généralement difficiles à mettre en œuvre et ne garantissent pas la précision requise pour certaines applications. L'objectif de cette thèse est donc d'étudier, modéliser et proposer un étalonnage précis et facile à mettre en œuvre de ces 2 types d'erreur des caméras Temps-de-Vol. Pour la modélisation du bruit comme pour la distorsion de la mesure de profondeur, deux solutions sont proposées présentant chacune une solution à un problème différent. La première vise à fournir un modèle précis alors que le second favorise la simplicité de la mise en œuvre. Ainsi, pour le bruit, alors que la majorité des modèles reposent uniquement sur l'information d'amplitude, nous proposons un premier modèle qui intègre aussi la position du pixel dans l'image. Pour encore une meilleure précision, nous proposons un modèle où l'amplitude est remplacée par la profondeur de l'objet et le temps d'intégration. S'agissant de la distorsion de la mesure de profondeur, nous proposons une première solution basée sur un modèle non-paramétrique garantissant une meilleure précision. Ensuite, pour fournir une solution plus facile à mettre en œuvre que la précédente et que celles de l'état de l'art, nous nous basons sur la connaissance à priori de la géométrie planaire de la scène observée3D cameras open new possibilities in different fields such as 3D reconstruction, Augmented Reality and video-surveillance since they provide depth information at high frame-rates. However, they have limitations that affect the accuracy of their measures. In particular for TOF cameras, two types of error can be distinguished : the stochastic camera noise and the depth distortion. In state of the art of TOF cameras, the noise is not well studied and the depth distortion models are difficult to use and don't guarantee the accuracy required for some applications. The objective of this thesis is to study, to model and to propose a calibration method of these two errors of TOF cameras which is accurate and easy to set up. Both for the noise and for the depth distortion, two solutions are proposed. Each of them gives a solution for a different problem. The former aims to obtain an accurate model. The latter, promotes the simplicity of the set up. Thereby, for the noise, while the majority of the proposed models are only based on the amplitude information, we propose a first model which integrate also the pixel position in the image. For a better accuracy, we propose a second model where we replace the amplitude by the depth and the integration time. Regarding the depth distortion, we propose a first solution based on a non-parametric model which guarantee a better accuracy. Then, we use the prior knowledge of the planar geometry of the observed scene to provide a solution which is easier to use compared to the previous one and to those of the litterature
28
Assunção, Guilherme Puglia. "Representações retangulares de grafos planares." Universidade de São Paulo, 2012. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-07052012-164622/.
Full textAbstract:
Uma representação retangular de um grafo plano G é uma representação de G, onde cada vértice é desenhado como um retângulo de modo que dois retângulos devem compartilhar algum segmento de seus lados se e somente se existe uma aresta em G entre os vértices correspondentes aos retângulos. Ainda, a representação de G deve formar um retângulo e não deve existir buracos, ou seja, toda região interna deve corresponder a algum vértice de G. Um desenho retangular de um grafo plano H é um desenho de H, onde todas as arestas são desenhadas como segmentos horizontais ou verticais. Ainda, todas as faces internas são retângulos e as arestas que incidem na face externa também formam um retângulo. Nesta dissertação, apresentamos os principais trabalhos existentes na literatura para problemas associados à representação retangular. Também apresentamos resultados para problemas associados ao desenho retangular. Por fim, apresentamos o algoritmo que desenvolvemos para determinar as coordenadas dos vértices de um desenho retangular quando a orientação das arestas já foram determinadas.A rectangular representation of a plane graph G is a representation of G, where each vertex is drawn as a rectangle, such as two rectangles have to share some boundary if and only if exist an edge in G between the corresponding vertices. Also, the representation of G must form a rectangle and does not contain any holes, in other words, every point inside the formed rectangle must correspond to some vertex of G. A rectangular drawing of a plane graph H is a drawing of H, where all edges are drawn either in vertical or in horizontal. Also, every internal face is a rectangle and the edges which are incident in the external face define a rectangle. In this dissertation, we present the main studies in the literature for problems associated with the rectangular representation. We also present results for problems associated with rectangular drawing. Finally, we present the algorithm we developed to determine the coordinates of the vertices of a rectangular drawing when the orientation of the edges have been determined.
29
Mori, Ricardo de Almeida. "Grafos : planaridade e projeto de ensino." reponame:Repositório Institucional da UFABC, 2015.
Find full textAbstract:
Orientador: Prof. Dr. Rafael de Mattos GrisiDissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Mestrado Profissional em Matemática em Rede Nacional, 2015.
Este trabalho apresenta uma introdução ao estudo da Teoria dos Grafos, com um dicionário visual e um histórico detalhado das origens deste ramo da matemática. Será dada uma ênfase especial ao estudo de grafos planares e na imersão de grafos em outras superfícies. Por fim, é apresentado um plano de aula para o professor interessado em introduzir o ensino de grafos a alunos do ensino fundamental e médio.
This paper presents an introduction to the study of Graph Theory, with a visual dictionary and a detailed history of the origins of this branch of mathematics. It will be given a special emphasis on the study of planar graphs and also in immersion graphs in other surfaces. Finally, we present a lesson plan for teacher interested in introducing the teaching of graphs to students of primary and secondary education.
30
Carson, D. I. "Planarity testing and embedding algorithms." Thesis, 1990. http://hdl.handle.net/10413/7865.
Full textAbstract:
This thesis deals with several aspects of planar graphs, and some of the problems associated with non-planar graphs. Chapter 1 is devoted to introducing some of the fundamental notation and tools used in the remainder of the thesis. Graphs serve as useful models of electronic circuits. It is often of interest to know if a given electronic circuit has a layout on the plane so that no two wires cross. In Chapter 2, three efficient algorithms are described for determining whether a given 2-connected graph (which may model such a circuit) is planar. The first planarity testing algorithm uses a path addition approach. Although this algorithm is efficient, it does not have linear complexity. However, the second planarity testing algorithm has linear complexity, and uses a recursive fragment addition technique. The last planarity testing algorithm also has linear complexity, and relies on a relatively new data structure called PQ-trees which have several important applications to planar graphs. This algorithm uses a vertex addition technique. Chapter 3 further develops the idea of modelling an electronic circuit using a graph. Knowing that a given electronic circuit may be placed in the plane with no wires crossing is often insufficient. For example, some electronic circuits often have in excess of 100 000 nodes. Thus, obtaining a description of such a layout is important. In Chapter 3 we study two algorithms for obtaining such a description, both of which rely on the PQ-tree data structure. The first algorithm determines a rotational embedding of a 2-connected graph. Given a rotational embedding of a 2-connected graph, the second algorithm determines if a convex drawing of a graph is possible. If a convex drawing is possible, then we output the convex drawing. In Chapter 4, we concern ourselves with graphs that have failed a planarity test of Chapter 2. This is of particular importance, since complex electronic circuits often do not allow a layout on the plane. We study three different ways of approaching the problem of an electronic circuit modelled on a non-planar graph, all of which use the PQ-tree data structure. We study an algorithm for finding an upper bound on the thickness of a graph, an algorithm for determining the subgraphs of a non-planar graph which are subdivisions of the Kuratowski graphs K5 and K3,3, and lastly we present a new algorithm for finding an upper bound on the genus of a non-planar graph.Thesis (M.Sc.)-University of Natal, Durban,1990.
31
Bachmaier, Christian [Verfasser]. "Circle planarity of level graphs / Christian Bachmaier." 2004. http://d-nb.info/973953985/34.
Full text
32
Percan, Merijam [Verfasser]. "Constrained planarity and augmentation problems / vorgelegt von Merijam Percan." 2007. http://d-nb.info/989561445/34.
Full text
33
Chen, Chunta, and 陳俊達. "Forecasting Model of Post CMP Planarity with Pad Properties." Thesis, 2003. http://ndltd.ncl.edu.tw/handle/70992642119388942625.
Full textAbstract:
碩士國立交通大學
科技管理學程碩士班
91
Selective oxide CMP methods like ILD and PMD CMP are commonly used in achieving global planarization for schemes of quarter micron processes and beyond. PMD & ILD CMP process offers great advantages in processing devices with better global planarity, enabling the use of additional metal layers on a chip manufacturing, tighter dimensional control in lithography, and enhancing yield by improving planarity to reduce the probability of metal stringers after metal damascene polishing. In PMD planarization using CMP method, the post CMP planarity is extremely sensitive to the pad properties and polishing tools employed. Polyurethane pads are commonly used for dielectric CMP application. Almost all the polishing performances like removal rate, WIWNU, WIDNU, defectivity, and planarity are strongly correlated with polishing pad properties. In this paper, we performed the statistic analytical method on the CMP behavior and try to set up a model to predict the post CMP planarity. The regression models which correlate polishing pad physical properties with post CMP wafer planarity have been explored for PMD CMP by using traditional Statistic Correlation and Grey Correlation analysis in this paper. As the polishing data quantity is limited, we find that Grey theory performs better in linear regression variable decision. By the step height regression model, we can get a clear picture about the influence of pad properties on post CMP step height. We find that stacked pad deflection and hardness are two major pad properties controlling the post CMP planarity. By examining the correlation of stacked hardness and deflection, these two properties are not totally independent to each other and the correlation is not low. This explains the model built with deflection and stacked thickness yield better fitness than the model built with stacked hardness and deflection both on Mirra and 6DS polishers. In conclusion, regression models derived from Grey Correlation analysis offer excellent fitting on post CMP planarity in this study.
34
Ray, Rahul [Verfasser]. "Geometric algorithms for object placement and planarity in a terrain / Rahul Ray." 2004. http://d-nb.info/97231623X/34.
Full text
35
Naff, Keaton. "Planarity and the mean curvature flow of pinched submanifolds in higher codimension." Thesis, 2021. https://doi.org/10.7916/d8-cmmq-7d42.
Full textAbstract:
In this thesis, we explore the role of planarity in mean curvature flow in higher codimension and investigate its implications for singularity formation in a certain class of flows. In Chapter 1, we show that the blow-ups of compact 𝑛-dimensional solutions to mean curvature flow in ℝⁿ initially satisfying the pinching condition |𝐴|² < c |𝐻|² for a suitable constant c = c(𝑛) must be codimension one. We do this by establishing a new a priori estimate via a maximum principle argument.
In Chapter 2, we consider ancient solutions to the mean curvature flow in ℝⁿ⁺¹ (𝑛 ≥ 3) that are weakly convex, uniformly two-convex, and satisfy derivative estimates |∇𝐴| ≤ 𝛾1 |𝐻|², |∇² 𝐴| \leq 𝛾2 |𝐻|³. We show that such solutions are noncollapsed. The proof is an adaptation of the foundational work of Huisken and Sinestrari on the flow of two-convex hypersurfaces. As an application, in arbitrary codimension, we classify the singularity models of compact 𝑛-dimensional (𝑛 ≥ 5) solutions to the mean curvature flow in ℝⁿ that satisfy the pinching condition |𝐴|² < c |𝐻|² for c = min {1/𝑛-2, 3(𝑛+1)/2𝑛(𝑛+2)}. Using recent work of Brendle and Choi, together with the estimate of Chapter 1, we conclude that any blow-up model at the first singular time must be a codimension one shrinking sphere, shrinking cylinder, or translating bowl soliton.
Finally, in Chapters 3 and 4, we prove a canonical neighborhood theorem for the mean curvature flow of compact 𝑛-dimensional submanifolds in ℝⁿ (𝑛 ≥ 5) satisfying a pinching condition |𝐴|² < c |𝐻|² for $c = min {1/𝑛-2, 3(𝑛+1)/2𝑛(𝑛+2)}. We first discuss, in some detail, a well-known compactness theorem of the mean curvature flow. Then, adapting an argument of Perelman and using the conclusions of Chapter 2, we characterize regions of high curvature in the pinched solutions of the mean curvature flow under consideration.
36
Anderson, Terry David. "The Vulcan game of Kal-toh: Finding or making triconnected planar subgraphs." Thesis, 2011. http://hdl.handle.net/10012/5882.
Full textAbstract:
In the game of Kal-toh depicted in the television series Star Trek: Voyager, players
attempt to create polyhedra by adding to a jumbled collection of metal rods. Inspired by
this fictional game, we formulate graph-theoretical questions about polyhedral (triconnected and planar) subgraphs in an on-line environment. The problem of determining the existence of a polyhedral subgraph within a graph G is shown to be NP-hard, and we also give some non-trivial upper bounds for the problem of determining the minimum number of edge additions necessary to guarantee the existence of a polyhedral subgraph in G. A two-player
formulation of Kal-toh is also explored, in which the first player to form a target subgraph is declared the winner. We show a polynomial-time solution for simple cases of this game but conjecture that the general problem is NP-hard.
37
Hora, Martin. "Složitost kreslení grafů s omezeními." Master's thesis, 2019. http://www.nusl.cz/ntk/nusl-397633.
Full textAbstract:
A labeled embedding of a planar graph G is a pair (G, g) consisting of a planar drawing G of G and a function g assigning labels (colors) to the faces of G. We study the problem of Embedding Restriction Satisfiability (ERS) that investi- gates whether a given graph has a labeled embedding satisfying a provided set of conditions. ERS is a relatively new problem, so not much is known about it. Nevertheless, it has great potential. It generalizes several problems looking for a particular drawing of a planar graph, such as the problem of Partially Embedded Planarity. Therefore, ERS may become a focal point in the area of graph draw- ing. In this thesis, we examine the computational complexity of ERS. We show that ERS is NP-complete. After that, we look at the complexity of some specific classes of its instances. We try to locate the boundary between the NP-complete and the polynomial variants of the problem. 1