No description available.

No description available.

No description available.

No description available.

The vertex separation of a graph is the minimum vertex separation of a linear layout of that graph over all its linear layouts. A linear layout of a graph is an arrangement of its vertices in a line and the vertex separation of a linear layout is maximum number of vertices to the left of any intervertex "gap" that are adjacent to vertices to the right of that gap, over all gaps. A unicyclic graph is a connected graph with precisely one cycle that is, a tree plus an extra edge. We present a O(n lgn) algorithm to compute the optimal vertex separation of unicyclic graphs. The algorithm is "practical" in the sense that it is easily implementable. Furthermore, the algorithm outputs a layout for the unicyclic graph of minimum vertex separation.

No description available.

Effective visualization of graphs is a powerful tool to help understand the relationships among the graph's underlying objects and to interact with them. Several styles for drawing graphs have emerged over the last three decades. Polyline drawing is a widely used style for drawing graphs, where each node is mapped to a distinct point in the plane and each edge is mapped to a polygonal chain between their corresponding nodes. Some common optimization criteria for such a drawing are defined in terms of area requirement, number of bends per edge, angular resolution, number of distinct line segments, edge crossings, and number of planar layers. In this thesis we develop algorithms for drawing graphs that optimize different aesthetic qualities of the drawing. Our algorithms seek to simultaneously optimize multiple drawing aesthetics, reveal potential trade-offs among them, and improve many previous graph drawing algorithms. We start by exploring probable trade-offs in the context of planar graphs. We prove that every $n$-vertex planar triangulation $G$ with maximum degree $\Delta$ can be drawn with at most $2n+t-3$ segments and $O(8^t \cdot \Delta^{2t})$ area, where $t$ is the number of leaves in a Schnyder tree of $G$. We then show that one can improve the area by allowing the edges to have bends. Since compact drawings often suffer from bad angular resolution, we seek to compute polyline drawings with better angular resolution. We develop a polyline drawing algorithm that is simple and intuitive, yet implies significant improvement over known results. At this point we move our attention to drawing nonplanar graphs. We prove that every thickness-$t$ graph can be drawn on $t$ planar layers with $\min\{O(2^{t/2} \cdot n^{1-1/\beta}), 2.25n +O(1)\}$ bends per edge, where $\beta = 2^{\lceil (t-2)/2 \rceil }$. Previously, the bend complexity, i.e., the number of bends per edge, was not known to be sublinear for $t>2$. We then examine the case when the number of available layers is restricted. The layers may now contain edge crossings. We develop a technique to draw complete graphs on two layers, which improves previous upper bounds on the number of edge crossings in such drawings. / October 2016

La présente thèse concerne l’étude structurelle pour le recouvrement du défaut par l’approche du bond graph. L'objectif est d'exploiter les propriétés structurelles et causales de l'outil bond graph, afin d’effectuer à la fois le diagnostic et l’analyse de la commande du système physique en présence du défaut. En effet, l’outil bond graph permet de vérifier les conditions structurelles de recouvrement de défauts pas seulement du point de vue de l’analyse de commande, mais aussi en considérant les informations issues de l’étape de diagnostic. Par conséquent, l’ensemble des défauts tolérés est obtenu en mode hors-ligne avant d’effectuer une implémentation réelle. En outre, en estimant le défaut comme une puissance perturbatrice fournie au système, ce qui permet d’étendre les résultats d’analyse structurelle pour le recouvrement du défaut à une compensation locale adaptative, directement à partir du modèle bond graph. Enfin, les résultats obtenus sont validés dans une application d’un véhicule autonome intelligent redondant. / This work deals with structural fault recoverability analysis using the bond graph model. The objective is to exploit the structural and causal properties of the bond graph tool in order to perform both diagnosis and control analysis in the presence of faults. Indeed, the bond graph tool enables to verify the structural conditions of fault recoverability not only from a control perspective but also from a diagnosis one. In this way, the set of faults that can be recovered is obtained previous to industrial implementation. In addition, a novel way to estimate the fault by a disturbing power furnished to the system, enabled to extend the results of structural fault recoverability by performing a local adaptive compensation directly from the bond graph model. Finally, the obtained structural results are validated on a redundant intelligent autonomous vehicle.

La présente thèse concerne l’étude structurelle d’un système modélisé par Bond Graph du point de vue détection et isolation de défaut. En combinant la théorie du module avec les propriétés causales et structurelles de l’outil BG, de simples conditions graphiques permettant de conclure sur la détectabilité et l’isolabilité de défauts composant ont été proposées. Aussi,une procédure de placement de capteur optimal a été présentée pour le recouvrement de la surveillabilité du système en présence de défauts. Pour l’étape de diagnostic, une procédure systématique a été développée pour la génération des indicateurs de défauts sensibles aux défauts composants considérés. L’approche proposée dans ce travail a été validé par une application sur un quart de véhicule autonome intelligent. / This thesis is concerned with system structural analyses for fault detection and isolation. By using the module theory and the causal and structural properties of the Bond Graph tool, simple graphical conditions of structural detectability and isolability of plant faults are proposed. Also, a procedure for optimal sensor placement is performed in order to recover systems monitorability in the presence of plant faults. Moreover, for the diagnosis step, a procedure is proposed for a systematic generation of faults indicator which are only sensitive to the desired plant faults. The proposed approach in this work is validated by an application on a quarter of an autonomous intelligent vehicle.

Ph.D. (Mathematics) / Please refer to full text to view abstract