Let K be a class of graphs. A pair (F,U) is a finite duality in K if U∈K, F is a finite set of graphs, and for any graph G in K we have G≤U if and only if F≤≰G for all F∈F, where "≤" is the homomorphism order. We also say U is a dual graph in K. We prove that the class of planar graphs has no finite dualities except for two trivial cases. We also prove that the class of toroidal graphs has no 5-colorable dual graphs except for two trivial cases. In a sharp contrast, for a higher genus orientable surface S we show that Thomassen's result (Thomassen, 1997 [17]) implies that the class, G(S), of all graphs embeddable in S has a number of finite dualities. Equivalently, our first result shows that for every planar core graph H except K1 and K4, there are infinitely many minimal planar obstructions for H-coloring (Hell and Nešetřil, 1990 [4]), whereas our later result gives a converse of Thomassen's theorem (Thomassen, 1997 [17]) for 5-colorable graphs on the torus.

Cette thèse traite de la segmentation et du suivi de structures curvilinéaires. La méthodologie proposée est appliquée à la segmentation et au suivi des guide-fils durant les interventions d'angioplastie. Pendant ces opérations, les cardiologues s'assurent que le positionnement des différents outils est correct au moyen d'un système d'imagerie fluoroscopique temps-réel. Les images obtenues sont très bruitées et les guides sont, en conséquence, particulièrement difficiles à segmenter. Les contributions de cette thèse peuvent être regroupées en trois parties. La première est consacrée à la détection des guides, la seconde a leur segmentation et la dernière a leur suivi. La détection partielle des guide-fils est réalisée soit par la sélection d'un opérateur de filtrage approprié soit en utilisant des méthodes modernes d'apprentissage artificiel. Dans un premier temps, un système réalisant un Boosting asymétrique pour entraîner un détecteur de guides est présenté. Par la suite, une méthode renforçant la réponse d'un filtre orientable au moyen d'une variante efficace de vote tensoriel est décrite. Dans la seconde partie, une approche ascendante est proposée, qui consiste à regrouper des points sélectionnés par le détecteur de fil, à extraire des primitives des agrégats obtenus et a les lier. Deux procédures locales de regroupement des points sont étudiées : une reposant sur un clustering de graphe non supervisé suivi d'une extraction de segments de droites ; et l'autre reposant sur un modèle graphique puis une extraction d'axe central. Par la suite, deux méthodes de liaison des primitives sont étudiées : la première repose sur une approche de programmation linéaire, et la seconde sur une heuristique de recherche locale. Dans la dernière partie, des méthodes de recalage sont utilisées pour améliorer la segmentation et pour suivre les fils. Le suivi propos'e couple un suivi iconique avec un suivi géométrique contenant un modèle prédictif. Cette méthode utilise un modèle graphique déterminant à la fois une position du guide-fil (segmentation) et des correspondances (tracking). La solution optimale de ce modèle graphique décrit simultanément les déplacements du guide-fil et les appariements entre points d'intérêt qui en sont extraits, fournissant ainsi une estimation robuste des déformations du fil par rapport aux grands déplacements et au bruit.

RODRIGUES, Jamires Ximenes. Superfícies orientáveis. 2017. 64 f. Dissertação (Mestrado Profissional em Matemática em Rede Nacional) - Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2017. / Submitted by Jessyca Silva (jessyca@mat.ufc.br) on 2017-09-06T19:45:45Z No. of bitstreams: 1 2017_dis_jxrodrigues.pdf: 1541911 bytes, checksum: 16ceb535d5195a8d469a18be46c393d6 (MD5) / Rejected by Rocilda Sales (rocilda@ufc.br), reason: Bom dia, Estou devolvendo a dissertação de JAMIRES XIMENES RODRIGUES, pois há alguns elementos do texto que precisão ser alterados: 1- FICHA CATALOGRÁFICA ( está faltando a ficha catalográfica do trabalho, a mesma poderá ser elaborada no sistema CATALOG, no endereço eletrônico: http://fichacatalografica.ufc.br/ OBS.: a página em PDF com a ficha catalográfica deverá ser inserida antes da folha de aprovação. 2- REFERÊNCIAS e BIBLIOGRAFIA ( as referências a autores no interior do trabalho e a listagem bibliografica não estão de acordo com o padrão ABNT: No interior do texto, uma das formas de fazer referência a um autor é colocar o último sobrenome do mesmo e o ano da publicação. Ex: Lima (2010), e não Carmo [2] ou apenas um número aleatório, Ex: [8]. Além disso a listagem da Bibliografia não deve estar numerada, de acordo com o padrão ABNT. Assim retire a numeração progressiva da bibliografia e utilize outro meio para associar o link às referências no interior do texto. Atenciosamente, on 2017-09-08T11:47:07Z (GMT) / Submitted by Jessyca Silva (jessyca@mat.ufc.br) on 2017-09-11T14:42:21Z No. of bitstreams: 1 2017_dis_jxrodrigues.pdf: 1544364 bytes, checksum: dae77589d6bbe5a94020860940a57c83 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2017-09-11T15:28:53Z (GMT) No. of bitstreams: 1 2017_dis_jxrodrigues.pdf: 1544364 bytes, checksum: dae77589d6bbe5a94020860940a57c83 (MD5) / Made available in DSpace on 2017-09-11T15:28:53Z (GMT). No. of bitstreams: 1 2017_dis_jxrodrigues.pdf: 1544364 bytes, checksum: dae77589d6bbe5a94020860940a57c83 (MD5) Previous issue date: 2017 / This work aims to present the concept of surfaces in Euclidean space and to present examples, starting from simpler cases as two-dimensional surfaces in R3, to general cases of m-dimensional surfaces in Rn. It is an introduction to the differential geometry of surfaces and of fundamental importance in the study of differentiable manifolds. The purpose is to prepare the reader for a connection with Riemannian geometry, an indispensable subject for masters and doctoral students in Mathematics. For a satisfactory understanding of this work it is necessary to be familiar with concepts of multivariable calculus and basic concepts of linear algebra. In addition, the present study presents the notion of orientable surface and non-orientable surface, presenting examples of each of these types of surfaces. / Esse trabalho tem como objetivo apresentar o conceito de superfícies no espaço euclidiano e apresentar exemplos, partindo de casos mais simples como superfícies bidimensionais em R3, a casos gerais de superfícies m-dimensionais em Rn. Trata-se de uma introdução à geometria diferencial de superfícies e de fundamental importância no estudo das variedades diferenciáveis. O propósito é preparar o leitor para uma conexão com a geometria riemanniana, estudo indispensável para alunos de mestrado e doutorado em matemática. Para um entendimento satisfatório desse trabalho é necessário estar familiarizado com conceitos de cálculo de várias variáveis e conceitos básicos de álgebra linear. Além disso, o presente estudo apresenta a noção de superfície orientável e superfície não orientável, apresentando exemplos de cada um desses tipos de superfícies.

Digital encoders are electro-mechanical sensors that measure linear or angular position using special binary patterns. The properties of these patterns influence the traits of the resulting encoders, such as their maximum speed, resolution, tolerance to error, or cost to manufacture. We describe a novel set of patterns that can be used in encoders that are simple and compact, but require some initial movement to register their position. Previous designs for such encoders, called absolute incremental encoders, tend to incorporate separate patterns for the functions of tracking incremental movement and determining the absolute position. The encoders in this work, however, use a single pattern that performs both functions, which maximizes information density and yields better resolution. Compared to existing absolute encoders, these absolute incremental encoders are much simpler with fewer pattern tracks and read heads, potentially allowing for lower-cost assembly of high resolution encoders. Furthermore, as the manufacturing requirements are less stringent, we expect such encoders may be suitable for use in D.I.Y. %27maker%27 projects, such as those undertaken recently by our lab.

We discuss a method of classifying 2-dimensional invertible topological quantum field theories (TQFTs) whose domain surface categories allow non-orientable cobordisms. These are known as Klein TQFTs. To this end we study the 1+1 dimensional open-closed unoriented cobordism category K, whose objects are compact 1-manifolds and whose morphisms are compact (not necessarily orientable) cobordisms up to homeomorphism. We are able to compute the fundamental group of its classifying space BK and, by way of this result, derive an infinite loop splitting of BK, a classification of functors K → Z, and a classification of 2-dimensional open-closed invertible Klein TQFTs. Analogous results are obtained for the two subcategories of K whose objects are closed or have boundary respectively, including classifications of both closed and open invertible Klein TQFTs. The results obtained throughout the paper are generalisations of previous results by Tillmann [Til96] and Douglas [Dou00] regarding the 1+1 dimensional closed and open-closed oriented cobordism categories. Finally we consider how our results should be interpreted in terms of the known classification of 2-dimensional TQFTs in terms of Frobenius algebras.

A model for DNA recombination uses 4-valent rigid vertex graphs, called assembly graphs. An assembly graph, similarly to the projection of knots, can be associated with an unsigned Gauss code, or double occurrence word. We define biologically motivated reductions that act on double occurrence words and, in turn, on their associated assembly graphs. For every double occurrence word w there is a sequence of reduction operations that may be applied to w so that what remains is the empty word, [epsilon]. Then the nesting index of a word w, denoted by NI(w), is defined to to be the least number of reduction operations necessary to reduce w to [epsilon]. The nesting index is the first property of assembly graphs that we study. We use chord diagrams as tools in our study of the nesting index. We observe two double occurrence words that correspond to the same circle graph, but that have arbitrarily large differences in nesting index values. In 2012, Buck et al. considered the cellular embeddings of assembly graphs into orientable surfaces. The genus range of an assembly graph [Gamma], denoted gr([Gamma]), was defined to be the set of integers g where g is the genus of an orientable surface F into which [Gamma] cellularly embeds. The genus range is the second property of assembly graphs that we study. We generalize the notion of the genus range to that of the genus spectrum, where for each g [isin] gr([Gamma]) we consider the number of orientable surfaces F obtained from [Gamma] by a special construction, called a ribbon graph construction, that have genus g. By considering this more general notion we gain a better understanding of the genus range property. Lastly, we show how one can obtain the genus spectrum of a double occurrence word from the genus spectrums of its irreducible parts, i.e., its double occurrence subwords. In the final chapter we consider constructions of double occurrence words that recognize certain values for nesting index and genus range. In general, we find that for arbitrary values of nesting index [ge] 2 and genus range, there is a double occurrence word that recognizes those values.

Cette thèse traite de la segmentation et du suivi de structures curvilinéaires. La méthodologie proposée est appliquée à la segmentation et au suivi des guide-fils durant les interventions d’angioplastie. Pendant ces opérations, les cardiologues s’assurent que le positionnement des différents outils est correct au moyen d’un système d’imagerie fluoroscopique temps-réel. Les images obtenues sont très bruitées et les guides sont, en conséquence, particulièrement difficiles à segmenter. Les contributions de cette thèse peuvent être regroupées en trois parties. La première est consacrée à la détection des guides, la seconde a leur segmentation et la dernière a leur suivi. La détection partielle des guide-fils est réalisée soit par la sélection d’un opérateur de filtrage approprié soit en utilisant des méthodes modernes d’apprentissage artificiel. Dans un premier temps, un système réalisant un Boosting asymétrique pour entraîner un détecteur de guides est présenté. Par la suite, une méthode renforçant la réponse d’un filtre orientable au moyen d’une variante efficace de vote tensoriel est décrite. Dans la seconde partie, une approche ascendante est proposée, qui consiste à regrouper des points sélectionnés par le détecteur de fil, à extraire des primitives des agrégats obtenus et a les lier. Deux procédures locales de regroupement des points sont étudiées : une reposant sur un clustering de graphe non supervisé suivi d’une extraction de segments de droites ; et l’autre reposant sur un modèle graphique puis une extraction d’axe central. Par la suite, deux méthodes de liaison des primitives sont étudiées : la première repose sur une approche de programmation linéaire, et la seconde sur une heuristique de recherche locale. Dans la dernière partie, des méthodes de recalage sont utilisées pour améliorer la segmentation et pour suivre les fils. Le suivi propos´e couple un suivi iconique avec un suivi géométrique contenant un modèle prédictif. Cette méthode utilise un modèle graphique déterminant à la fois une position du guide-fil (segmentation) et des correspondances (tracking). La solution optimale de ce modèle graphique décrit simultanément les déplacements du guide-fil et les appariements entre points d’intérêt qui en sont extraits, fournissant ainsi une estimation robuste des déformations du fil par rapport aux grands déplacements et au bruit. / This thesis addresses the segmentation and the tracking of thin curvilinear structures. The proposed methodology is applied to the delineation and the tracking of the guide-wires that are used during cardiac angioplasty. During these interventions, cardiologists assess the displacement of the different devices with a real-time fluoroscopic imaging system. The obtained images are very noisy and, as a result, guide-wires are particularly challenging to segment and track. The contributions of this thesis can be grouped into three parts. The first part is devoted to the detection of the guide-wires, the second part addresses their segmentation and the last part focuses on their spatio-temporal tracking. Partial detection of guide-wires is addressed either through the selection of appropriate filter operators or using modern machine learning methods. First, a learning framework using an asymmetric Boosting algorithm for training a guidewire detector is presented. A second method enhancing the output of a steerable filter by using an efficient tensor voting variant is then described. In the second part, a bottom-up method is proposed, that consists in grouping points selected by the wire detector, in extracting primitives from these aggregates and in linking these primitives together. Two local grouping procedures are investigated: one based on unsupervised graph-based clustering followed by a linesegment extraction and one based on a graphical model formulation followed by a graph-based centerline extraction. Subsequently, two variants of linking methods are investigated: one is based on integer programming and one on a local search heuristic. In the last part, registration methods are exploited for improving the segmentation via an image fusion method and then for tracking the wires. This latter is performed by a graph-based iconic tracking method coupled with a graphbased geometric tracking that encodes to certain extend a predictive model. This method uses a coupled graphical model that seeks both optimal position (segmentation) and spatio-temporal correspondences (tracking). The optimal solution of this graphical model simultaneously determines the guide-wire displacements and matches the landmarks that are extracted along it, what provides a robust estimation of the wire deformations with respect to large motion and noise.

Dans cette thèse, nous considérons des questions relatives aux homomorphismes de quatre types distincts de graphes : les graphes orientés, les graphes orientables, les graphes 2-arête colorés et les graphes signés. Pour chacun des ces quatre types, nous cherchons à déterminer le nombre chromatique, le nombre de clique relatif et le nombre de clique absolu pour différentes familles de graphes planaires : les graphes planaires extérieurs, les graphes planaires extérieurs de maille fixée, les graphes planaires et les graphes planaires de maille fixée. Nous étudions également les étiquetages "2-dipath" et "L(p,q)" des graphes orientés et considérons les catégories des graphes orientables et des graphes signés. Nous étudions enfin les différentes relations pouvant exister entre ces quatre types d'homomorphismes de graphes. / An oriented graph is a directed graph with no cycle of length at most two. A homomorphism of an oriented graph to another oriented graph is an arc preserving vertex mapping. To push a vertex is to switch the direction of the arcs incident to it. An orientable graph is an equivalence class of oriented graph with respect to the push operation. An orientable graph [−→G] admits a homomorphism to an orientable graph [−→H] if an element of [−→G] admits a homomorphism to an element of [−→H]. A signified graph (G, Σ) is a graph whose edges are assigned either a positive sign or a negative sign, while Σ denotes the set of edges with negative signs assigned to them. A homomorphism of a signified graph to another signified graph is a vertex mapping such that the image of a positive edge is a positive edge and the image of a negative edge is a negative edge. A signed graph [G, Σ] admits a homomorphism to a signed graph [H, Λ] if an element of [G, Σ] admits a homomorphism to an element of [H, Λ]. The oriented chromatic number of an oriented graph −→G is the minimum order of an oriented graph −→H such that −→G admits a homomorphism to −→H. A set R of vertices of an oriented graph −→G is an oriented relative clique if no two vertices of R can have the same image under any homomorphism. The oriented relative clique number of an oriented graph −→G is the maximum order of an oriented relative clique of −→G. An oriented clique or an oclique is an oriented graph whose oriented chromatic number is equal to its order. The oriented absolute clique number of an oriented graph −→G is the maximum order of an oclique contained in −→G as a subgraph. The chromatic number, the relative chromatic number and the absolute chromatic number for orientable graphs, signified graphs and signed graphs are defined similarly. In this thesis we study the chromatic number, the relative clique number and the absolute clique number of the above mentioned four types of graphs. We specifically study these three parameters for the family of outerplanar graphs, of outerplanar graphs with given girth, of planar graphs and of planar graphs with given girth. We also try to investigate the relation between the four types of graphs and prove some results regarding that. In this thesis, we provide tight bounds for the absolute clique number of these families in all these four settings. We provide improved bounds for relative clique numbers for the same. For some of the cases we manage to provide improved bounds for the chromatic number as well. One of the most difficult results that we prove here is that the oriented absolute clique number of the family of planar graphs is at most 15. This result settles a conjecture made by Klostermeyer and MacGillivray in 2003. Using the same technique we manage to prove similar results for orientable planar graphs and signified planar graphs. We also prove that the signed chromatic number of triangle-free planar graphs is at most 25 using the discharging method. This also implies that the signified chromatic number of trianglefree planar graphs is at most 50 improving the previous upper bound. We also study the 2-dipath and oriented L(p, q)-labeling (labeling with a condition for distance one and two) for several families of planar graphs. It was not known if the categorical product of orientable graphs and of signed graphs exists. We prove both the existence and also provide formulas to construct them. Finally, we propose some conjectures and mention some future directions of works to conclude the thesis.

Convexity in graphs has been widely discussed in graph theory and G. Chartrand et al. introduced the convexity number of oriented graphs in 2002. In this thesis, we follow the notions addressed by them and develop an extension in some related topics of convexity in directed graphs. Let D be a connected oriented graph. A set S subseteq V(D) is convex in D if, for every pair of vertices x, yin S, the vertex set of every x-y geodesic (x-y shortest directed path) and y-x geodesic in D is contained in S. The convexity number con(D) of a nontrivial oriented graph D is the maximum cardinality of a proper convex set of D. We show that for every possible triple n, m, k of integers except for k=4, there exists a strongly connected digraph D of order n, size m, and con(D)=k. Let G be a graph. We define the convexity spectrum S_{C}(G)={con(D): D is an orientation of G} and the strong convexity spectrum S_{SC}(G)={con(D): D is a strongly connected orientation of G}. Then S_{SC}(G) ⊆ S_{C}(G). We show that for any n ¡Ú 4, 1 ≤ a ≤ n-2 and a n ¡Ú 2, there exists a 2-connected graph G with n vertices such that S_C(G)=S_{SC}(G)={a,n-1}, and there is no connected graph G of order n ≥ 3 with S_{SC}(G)={n-1}. We also characterizes the convexity spectrum and the strong convexity spectrum of complete graphs, complete bipartite graphs, and wheel graphs. Those convexity spectra are of different kinds. Let the difference of convexity spectra D_{CS}(G)=S_{C}(G)- S_{SC}(G) and the difference number of convexity spectra dcs(G) be the cardinality of D_{CS}(G) for a graph G. We show that 0 ≤ dcs(G) ≤ ⌊|V(G)|/2⌋, dcs(K_{r,s})=⌊(r+s)/2⌋-2 for 4 ≤ r ≤ s, and dcs(W_{1,n-1})= 0 for n ≥ 5. The convexity spectrum ratio of a sequence of simple graphs G_n of order n is r_C(G_n)= liminflimits_{n to infty} frac{|S_{C}(G_n)|}{n-1}. We show that for every even integer t, there exists a sequence of graphs G_n such that r_C(G_n)=1/t and a formula for r_C(G) in subdivisions of G.

Dans cette thèse, nous considérons des questions relatives aux homomorphismes de quatre types distincts de graphes : les graphes orientés, les graphes orientables, les graphes 2-arête colorés et les graphes signés. Pour chacun des ces quatre types, nous cherchons à déterminer le nombre chromatique, le nombre de clique relatif et le nombre de clique absolu pour différentes familles de graphes planaires : les graphes planaires extérieurs, les graphes planaires extérieurs de maille fixée, les graphes planaires et les graphes planaires de maille fixée. Nous étudions également les étiquetages "2-dipath" et "L(p,q)" des graphes orientés et considérons les catégories des graphes orientables et des graphes signés. Nous étudions enfin les différentes relations pouvant exister entre ces quatre types d'homomorphismes de graphes.