The central topic of this thesis is Schnyder's Theorem. Schnyder's Theorem provides a characterization of planar graphs in terms of their poset dimension, as follows: a graph G is planar if and only if the dimension of the incidence poset of G is at most three. One of the implications of the theorem is proved by giving an explicit mapping of the vertices to R^2 that defines a straightline embedding of the graph. The other implication is proved by introducing the concept of normal labelling. Normal labellings of plane triangulations can be used to obtain a realizer of the incidence poset. We present an exposition of Schnyder’s theorem with his original proof, using normal labellings. An alternate proof of Schnyder’s Theorem is also presented. This alternate proof does not use normal labellings, instead we use some structural properties of a realizer of the incidence poset to deduce the result. Some applications and a generalization of one implication of Schnyder’s Theorem are also presented in this work. Normal labellings of plane triangulations can be used to obtain a barycentric embedding of a plane triangulation, and they also induce a partition of the edge set of a plane triangulation into edge disjoint trees. These two applications of Schnyder’s Theorem and a third one, relating realizers of the incidence poset and canonical orderings to obtain a compact drawing of a graph, are also presented. A generalization, to abstract simplicial complexes, of one of the implications of Schnyder’s Theorem was proved by Ossona de Mendez. This generalization is also presented in this work. The concept of order labelling is also introduced and we show some similarities of the order labelling and the normal labelling. Finally, we conclude this work by showing the source code of some implementations done in Sage.

The central topic of this thesis is Schnyder's Theorem. Schnyder's Theorem provides a characterization of planar graphs in terms of their poset dimension, as follows: a graph G is planar if and only if the dimension of the incidence poset of G is at most three. One of the implications of the theorem is proved by giving an explicit mapping of the vertices to R^2 that defines a straightline embedding of the graph. The other implication is proved by introducing the concept of normal labelling. Normal labellings of plane triangulations can be used to obtain a realizer of the incidence poset. We present an exposition of Schnyder’s theorem with his original proof, using normal labellings. An alternate proof of Schnyder’s Theorem is also presented. This alternate proof does not use normal labellings, instead we use some structural properties of a realizer of the incidence poset to deduce the result. Some applications and a generalization of one implication of Schnyder’s Theorem are also presented in this work. Normal labellings of plane triangulations can be used to obtain a barycentric embedding of a plane triangulation, and they also induce a partition of the edge set of a plane triangulation into edge disjoint trees. These two applications of Schnyder’s Theorem and a third one, relating realizers of the incidence poset and canonical orderings to obtain a compact drawing of a graph, are also presented. A generalization, to abstract simplicial complexes, of one of the implications of Schnyder’s Theorem was proved by Ossona de Mendez. This generalization is also presented in this work. The concept of order labelling is also introduced and we show some similarities of the order labelling and the normal labelling. Finally, we conclude this work by showing the source code of some implementations done in Sage.

In this thesis we study the following dimensional parameters : boxicity, cubicity, threshold dimension and poset dimension. While the first three parameters are defined on graphs, poset dimension is defined on partially ordered sets (or posets). We only consider finite graphs and posets. In addition, we assume that the graphs are simple and undirected. Boxicity and Cubicity: A k-box (k-cube) is a Cartesian product of closed intervals(unit-intervals) [a1,b1]x…x [ak,bk]. The boxicity (cubicity) of a graph G,box (G) (cub(G)) is the minimum integer k such that every vertex in G is mapped to a k-box(k-cube) in the k-dimensional Euclidean space and two boxes(cubes) intersect if and only if their corresponding vertices are adjacent in G. Boxicity and cubicity can be considered as extensions of the concept of interval graphs and unit-interval graphs respectively. Threshold Dimension: A graph G is a threshold graph if there is a real number p and a weight function w: V→ R such that for any two vertices u,,v ε V(G),{ u, v }is an edge if and only if w(u)+w(v) ≥ p. The threshold dimension of a graph G is the minimum integer k such that there exist k threshold graphs Gi, i =1,2,...,k which satisfy E(G)= E(G1)U E(G2)U….UE(Gk). Poset Dimension: Let P = (S, P)be a poset where S is a finite non-empty set and P is a reflexive, anti-symmetric and transitive binary relation on S. P is a total order if every pair of elements in S is comparable in P. The dimension of P , denoted by dim(P )is the minimum integer k such that there exist k total orders on S, L1,...,Lk and for two distinct elements x,y ε S: x < y in P if and only if x < y in each Li,i ε ,{1. 2,...,k } All the four dimensional parameters that we have considered are very hard to compute. It is NP-complete to even determine if the boxicity of a graph is at most 2, if its cubicity is at most 3, if its threshold dimension is at most 3 and if the dimension of a poset is at most 3. Also it is hard to design an approximation algorithm within √n factor for computing the dimension of a poset. OurResults We state some of our main results: 1. Lower bounds for boxicity: We have developed two general methods based on certain vertex isoperimetric properties of graphs for deriving lower bounds. Application of these methods has led to some significant results. We mention a few of them here: ( a) Almost all graphs have boxicity Ω(n). (b) For a fixed k, boxicity of random k-regular graphs is Ω(k/log k). 2. Consider a poset P = (S,P) and let GP be its underlying comparability graph. We show that for any poset P, box(GP)/(χ(GP) - 1) ≤ dim(P) ≤ 2box (GP), where χ(GP) is the chromatic number of GP and χ(GP) = 1. Some important consequences of this result are: (a) It allows us to derive hitherto unknown upper bounds for poset dimension such as dim(P) ≤ 2tree-width (GP) + 4. (b) The boxicity of any graph with maximum degree Δ is O (Δlog2 Δ) which is an improvement over the best known upper bound of Δ2 +2. (c) There exist graphs with boxicity Ω(ΔlogΔ). This disproves a conjecture that the boxicity of a graph is O(Δ). (d)There exists no polynomial-time algorithm to approximate the boxicity of a bipartite graph on n vertices within a factor of O(n0.5−ε)for any ε > 0, unless NP = ZPP. 3.We show that every poset can be associated with a split graph such that the threshold dimension of the complement of the split graph is equal to the dimension of the poset. As a consequence we show that there exists no polynomial-time algorithm to approximate the threshold dimension of a split graph on n vertices with a factor of O(n0.5−ε)for any ε > 0, unless NP= ZPP. 4.We have given an upper bound for the cubicity of interval graphs. Claw number of a graph G, ψ(G) is the largest positive integer m such that K1,m is an induced subgraph of G. If G is an interval graph, we show that [log2 ψ(G)] ≤ cub(G) ≤ min([log2 α ], [log2 ψ(G)] +2), where α is the independence number of G. 5.We have improved upper bounds for the dimension of incidence posets and interval orders which are among the well-studied classes of posets.

Dans cette thèse, nous abordons deux problèmes de théorie des graphes liés à deux problèmes biologiques de symbiose (deux organismes vivent en symbiose s'ils ont une interaction étroite et à long terme). Le premier problème est lié au phénomène de l'Incompatibilité cytoplasmique (IC) induit par certaines bactéries parasites chez leurs hôtes. L'IC se traduit par l'impossibilité de donner naissance à une progéniture saine lorsqu'un mâle infecté s'accouple avec une femelle non infectée. En termes de graphe ce problème peut s'interpréter comme la recherche d'une couverture minimum par des "sous-graphes des chaînes" d'un graphe biparti. Un graphe des chaînes est un graphe biparti dont les noeuds peuvent être ordonnés selon leur voisinage.En terme biologique, la taille minimale représente le nombre de facteurs génétiques impliqués dans le phénomène de l'IC. Dans la première moitié de la thèse, nous abordons trois problèmes connexes à ce modèle de la théorie des graphes. Le premier est l'énumération de tous les graphes des chaînes maximaux arêtes induits d'un graphe biparti G, pour lequel nous fournissons un algorithme en delai polynomial avec un retard de O(n^2m) où n est le nombre de noeuds et m le nombre d'arêtes de G. Dans la même section, nous montrons que (n/2)! et 2^(\sqrt{m}\log m) bornent le nombre de sous-graphes de chaînes maximales de G et nous les utilisons pour établir la complexité "input-sensitive" de notre algorithme. Le deuxième problème que nous traitons est de trouver le nombre minimum de graphes des chaînes nécessaires pour couvrir tous les bords d'un graphe biparti.Pour résoudre ce problème NP-hard, en combinant notre algorithme avec la technique d'inclusion-exclusion, nous fournissons un algorithme exponentiel exact en O^*((2+c)^m), pour chaque c > 0 (par O^* on entend la notation O standard mais en omettant les facteurs polynomiaux). Le troisième problème est l'énumération de toutes les couvertures minimales par des sous-graphes des chaînes. Nous montrons qu'il est possible d'énumérer toutes les couvertures minimales de G en temps O([(M + 1) |S|] ^ [\ log ((M + 1) |S|)]) où S est le nombre de couvertures minimales de G et M le nombre maximum des sous-graphes des chaînes dans une couverture minimale. Nous présentons ensuite la relation entre le second problème et le calcul de la dimension intervallaire d'un poset biparti. Nous donnons une interprétation de nos résultats dans le contexte de la dimension d'ordre / In this thesis, we address two graph theoretical problems connected to two different biological problems both related to symbiosis (two organisms live in symbiosis if they have a close and long term interaction). The first problem is related to the size of a minimum cover by "chain subgraphs" of a bipartite graph. A chain graph is a bipartite graph whose nodes can be ordered by neighbourhood inclusion. In biological terms, the size of a minimum cover by chain subgraphs represents the number of genetic factors involved in the phenomenon of Cytoplasmic Incompatibility (CI) induced by some parasitic bacteria in their insect hosts. CI results in the impossibility to give birth to an healthy offspring when an infected male mates with an uninfected female. In the first half of the thesis we address three related problems. One is the enumeration of all the maximal edge induced chain subgraphs of a bipartite graph G, for which we provide a polynomial delay algorithm with a delay of O(n^2m) where n is the number of nodes and m the number of edges of G. Furthermore, we show that (n/2)! and 2^(\sqrt{m} \log m) bound the number of maximal chain subgraphs of G and use them to establish the input-sensitive complexity of the algorithm. The second problem we treat is finding the minimum number of chain subgraphs needed to cover all the edges of a bipartite graph. To solve this NP-hard problem, we provide an exact exponential algorithm which runs in time O^*((2+c)^m), for every c>0, by a procedure which uses our algorithm and an inclusion-exclusion technique (by O^* we denote standard big O notation but omitting polynomial factors). Notice that, since a cover by chain subgraphs is a family of subsets of edges, the existence of an algorithm whose complexity is close to 2^m is not obvious. Indeed, the basic search space would have size 2^(2^m), which corresponds to all families of subsets of edges of a graph on $m$ edges. The third problem is the enumeration of all minimal covers by chain sugbgraphs. We show that it is possible to enumerate all such minimal covers of G in time O([(M+1)|S|]^[\log((M+1)|S|)]) where S is the number of minimal covers of G and M the maximum number of chain graphs in a minimal cover. We then present the relation between the second problem and the computation of the interval order dimension of a bipartite poset. We give an interpretation of our results in the context of poset and interval poset dimension... [etc]