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.

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.

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 (H2O2), 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 H2O2 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.

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ée. / 3D 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.

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

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.

Planar graphs have a rich history that dates back to the 18th Century. They form one of the core concepts of graph theory. In computational graph theory, they offer broad advantages to algorithm design and many groundbreaking results are based on them. Formally, a given graph is either planar or non-planar. However, there exists a diverse set of established measures to estimate how far away from being planar any given graph is. In this thesis, we aim at evaluating and improving algorithms to compute these measures of non-planarity. Particularly, we study (1) the problem of finding a maximum planar subgraph, i.e., a planar subgraph with the least number of edges removed; (2) the problem of embedding a graph on a lowest possible genus surface; and finally (3) the problem of drawing a graph such that there are as few edge crossings as possible. These problems constitute classical questions studied in graph drawing and each of them is NP-hard. Still, exact (exponential time) algorithms for them are of high interest and have been subject to study for decades. We propose novel mathematical programming models, based on different planarity criteria, to compute maximum planar subgraphs and low-genus embeddings. The key aspect of our most successful new models is that they carefully describe also the relation between embedded (sub-)graphs and their duals. Based on these models, we design algorithms that beat the respective state-of-the-art by orders of magnitude. We back these claims by extensive computational studies and rigorously show the theoretical advantages of our new models. Besides exact algorithms, we consider heuristic and approximate approaches to the maximum planar subgraph problem. Furthermore, in the realm of crossing numbers, we present an automated proof extraction to easily verify the crossing number of any given graph; a new hardness result for a subproblem that arises, e.g., when enumerating simple drawings; and resolve a conjecture regarding high node degree in minimal obstructions for low crossing number.

Languages occasionally have syntactic constructions that are difficult, if not impossible, to describe using a context-free grammar. One such construction is a crossing dependency. Crossing dependencies have been well studied for Dutch and Swiss German (Huybregts, 1976; Shieber, 1985), and recently for Tagalog (Maclachlan and Rambow, 2003). In this paper I propose that Persian exhibits crossing dependencies. In this SOV language, a light verb construction in the future tense becomes interrupted by a future auxiliary verb, which agrees with its subject in person and number. The future auxiliary also splits passive constructions in a similar manner. These forms present interesting challenges for computational models of language. I will discuss implications of this phenomenon within current formal and linguistic theories.

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.

Orientador: Prof. Dr. Rafael de Mattos Grisi / Dissertaçã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.