A t-spanner of a graph G is a subgraph H of G, which the distance between any two vertices in H is at most t times their distance in G. A tree t-spanner of G is a t-spanner which is a tree. In this dissertation, we discuss the t-spanners on trapezoid, permutation, and interval graphs. We first introduce an O(n) algorithm for finding a tree 4-spanner on trapezoid graphs. Then, give an O(n)algorithm for finding a tree 3-spanner on permutation graphs, improving the existed O(n + m) algorithm. Since the class of permutation graphs is a subclass of trapezoid graphs, we can apply the algorithm on permutation graphs to find the approximation of a tree 3-spanner on trapezoid graphs in O(n) time with edge bound 2n. Finally, we show that not all interval graphs have a tree 2-spanner.

abstract: Graph coloring is about allocating resources that can be shared except where there are certain pairwise conflicts between recipients. The simplest coloring algorithm that attempts to conserve resources is called first fit. Interval graphs are used in models for scheduling (in computer science and operations research) and in biochemistry for one-dimensional molecules such as genetic material. It is not known precisely how much waste in the worst case is due to the first-fit algorithm for coloring interval graphs. However, after decades of research the range is narrow. Kierstead proved that the performance ratio R is at most 40. Pemmaraju, Raman, and Varadarajan proved that R is at most 10. This can be improved to 8. Witsenhausen, and independently Chrobak and Slusarek, proved that R is at least 4. Slusarek improved this to 4.45. Kierstead and Trotter extended the method of Chrobak and Slusarek to one good for a lower bound of 4.99999 or so. The method relies on number sequences with a certain property of order. It is shown here that each sequence considered in the construction satisfies a linear recurrence; that R is at least 5; that the Fibonacci sequence is in some sense minimally useless for the construction; and that the Fibonacci sequence is a point of accumulation in some space for the useful sequences of the construction. Limitations of all earlier constructions are revealed. / Dissertation/Thesis / Ph.D. Mathematics 2010

A graph Gis said to be an intersection graph of sets from a family of sets if there exists a function ƒ : V(G)→ such that for u,v V(G), (u,v) E(G) ƒ (u) ƒ (v) ≠ . Interval graphs are thus the intersection graphs of closed intervals on the real line and unit interval graphs are the intersection graphs of unit length intervals on the real line. An interval on the real line can be generalized to a “kbox” in Rk.A kbox B =(R1,R2,...,Rk), where each Riis a closed interval on the real line, is defined to be the Cartesian product R1x R2x…x Rk. If each Ri is a unit length interval, we call B a k-cube. Thus, 1-boxes are just closed intervals on the real line whereas 2-boxes are axis-parallel rectangles in the plane. We study the intersection graphs of k-boxes and k-cubes. The parameter boxicity of a graph G, denoted as box(G), is the minimum integer k such that G is an intersection graph of k-boxes. Similarly, the cubicity of G, denoted as cub(G), is the minimum integer k such that G is an intersection graph of k-cubes. Thus, interval graphs are the graphs with boxicity at most 1 and unit interval graphs are the graphs with cubicity at most 1. These parameters were introduced by F. S.Roberts in 1969. In some sense, the boxicity of a graph is a measure of how different a graph is from an interval graph and in a similar way, the cubicity is a measure of how different the graph is from a unit interval graph. We prove several upper bounds on the boxicity and cubicity of general as well as special classes of graphs in terms of various graph parameters such as the maximum degree, the number of vertices and the bandwidth. The following are some of the main results presented. 1. We show that for any graph G with maximum degree Δ , box(G)≤ Δ 22 . This result implies that bounded degree graphs have bounded boxicity no matter how large the graph might be. 2. It was shown in [18] that the boxicity of a graph on n vertices with maximum degree Δ is O(Δ ln n). But a similar bound does not hold for the average degree davof a graph. [18] gives graphs in which the boxicity is exponentially larger than davln n. We show that even though an O(davln n) upper bound for boxicity does not hold for all graphs, for almost all graphs, boxicity is O(davln n). 3. The ratio of the cubicity to boxicity of any graph shown in [15] when combined with the results on boxicity show that cub(G) is O(Δ ln 2 n) and O(2 ln n) for any graph G on n vertices and with maximum degree . By using a randomized construction, we prove the better upper bound cub(G) ≤ [4(Δ + 1) ln n.] 4. Two results relating the cubicity of a graph to its bandwidth b are presented. First, it is shown that cub(G) ≤ 12(Δ + 1)[ ln(2b)] + 1. Next, we derive the upper bound cub(G) ≤ b + 1. This bound is used to derive new upper bounds on the cubicity of special graph classes like circular arc graphs, cocomparability graphs and ATfree graphs in relation to the maximum degree. 5. The upper bound for cubicity in terms of the bandwidth gives an upper bound of Δ + 1 for the cubicity of interval graphs. This bound is improved to show that for any interval graph G with maximum degree , cub(G) ≤[ log2 Δ] + 4. 6. Scheinerman [54] proved that the boxicity of any outerplanar graph is at most 2. We present an independent proof for the same theorem. 7. Halin graphs are planar graphs formed by adding a cycle connecting the leaves of a tree none of whose vertices have degree 2. We prove that the boxicity of any Halin graph is equal to 2 unless it is a complete graph on 4 vertices, in which case its boxicity is 1.

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.

本文針對2-連通的最大外平面圖，討論其有界容忍表示法，且找到禁止子圖S3。我們更進一步證明：如果一個2-連通的最大外平面圖恰有兩個點的度為2時，則此圖為區間圖。 / We prove that a 2-connected maximal outerplanar graph G is a bounded tolerance graph if and only if there is no induced subgraph S3 of G and G has no induced subgraph S3 if and only if G is an interval graph.

Beim Graphisomorphieproblem geht es um die Frage, ob zwei Graphen bis auf Knotenumbenennungen die gleiche Struktur haben. Es ist eines der wenigen verbleibenden natürlichen Probleme, für die weder ein Polynomialzeitalgorithmus noch NP-Härte bekannt ist. Aus dieser Situation ist ein Forschungszweig erwachsen, der effiziente Isomorphiealgorithmen für eingeschränkte Graphklassen entwickelt. Der Hauptbeitrag dieser Arbeit besteht in Logspace-Algorithmen, die das Isomorphieproblem für k-Bäume, Intervallgraphen, sowie Helly- und Proper-Kreisbogengraphen lösen. Dies verbessert zuvor bekannte parallele Algorithmen und führt zu einer vollständigen Klassifikation der Komplexität dieser Probleme, da für sie auch Logspace-Härte nachgewiesen wird. Tatsächlich leisten die vorgestellten Algorithmen mehr: Im Fall der k-Bäume berechnet der Algorithmus kanonische Knotenbenennungen mit O(k log n) Platz. Eine alternative Implementation des Algorithmus kommt mit O((k+1)!n) Zeit aus – hierbei ist n die Anzahl der Knoten – und ist damit der schnellste bekannte FPT-Algorithmus für Isomorphie von k-Bäumen. Die Algorithmen für Intervall- und Kreisbogengraphen berechnen kanonische Repräsentationen – das heißt, sie weisen jedem Knoten ein Intervall (beziehungsweise einen Kreisbogen) zu, sodass diese sich genau dann schneiden, wenn die zugehörigen Knoten benachbart sind, und isomorphe Eingabegraphen das gleiche Intervallmodell (beziehungsweise Kreisbogenmodell) erhalten. Außerdem werden auch Logspace-Algorithmen angegeben, die Intervallrepräsentationen mit zusätzlichen Eigenschaften berechnen – oder erkennen, dass dies nicht möglich ist: Für die resultierenden Intervallmodelle kann gefordert werden, dass sie proper sind (also kein Intervall ein anderes enthält), dass sie unit sind (also alle Intervalle die gleiche Länge haben) oder dass die Längen der paarweisen Schnitte (und optional der einzelnen Intervalle) vorgegebenen Werten entsprechen. / The graph isomorphism problem deals with the question if two graphs have the same structure up to renaming their vertices. It is one of the few remaining natural problems for which neither a polynomial-time algorithm nor NP-hardness is known. This situation has led to a branch of research that develops efficient algorithms for special cases of the graph isomorphism problem, where the input graphs are required to be from restricted graph classes. The main contribution of this thesis comprises of logspace algorithms that solve the isomorphism problem for k-trees, interval graphs, Helly circular-arc graphs and proper circular-arc graphs. This improves previously known parallel algorithms and leads to a complete classification of the complexity of these problems, as they are also shown to be hard for logspace. In fact, these algorithms achieve more: In the case of k-trees, the algorithm computes canonical labelings in space O(k log n). An alternative implementation runs in time O((k+1)!n), where n is the number of vertices, yielding the fastest known FPT algorithm for k-tree isomorphism. The algorithms for interval and circular-arc graphs actually compute canonical representations, i.e., each vertex is assigned an interval (or arc) such that these intersect each other if and only if the corresponding vertices are adjacent, and isomorphic input graphs receive the same interval (or arc) model. This thesis also presents logspace algorithms that compute interval representations with additional properties, or detect that this is not possible: The resulting interval models can be required to be proper (no interval contains another), unit (all intervals have the same length), or to satisfy prescribed lengths for pairwise intersections (and possibly prescribed lengths of intervals).

The boxicity of a graph G, denoted as box(G), is the minimum dimension d for which each vertex of G can be mapped to a d-dimensional axis-parallel box in Rd such that two boxes intersect if and only if the corresponding vertices of G are adjacent. An axis-parallel box is a generalized rectangle with sides parallel to the coordinate axes. If additionally, we restrict all sides of the rectangle to be of unit length, the new parameter so obtained is called the cubicity of the graph G, denoted by cub(G). F.S. Roberts had shown that for a graph G with n vertices, box(G) ≤ and cub(G) ≤ . A minimum vertex cover of a graph G is a minimum cardinality subset S of the vertex set of G such that each edge of G has at least one endpoint in S. We show that box(G) ≤ +1 and cub(G)≤ t+ ⌈log2(n −t)⌉−1 where t is the cardinality of a minimum vertex cover. Both these bounds are tight. For a bipartite graph G, we show that box(G) ≤ and this bound is tight. We observe that there exist graphs of very high boxicity but with very low chromatic num-ber. For example, there exist bipartite (2 colorable) graphs with boxicity equal to . Interestingly, if boxicity is very close to , then the chromatic number also has to be very high. In particular, we show that if box(G) = −s, s ≥ 02, then x(G) ≥ where X(G) is the chromatic number of G. We also discuss some known techniques for findingan upper boundon the boxicityof a graph -representing the graph as the intersection of graphs with boxicity 1 (boxicity 1 graphs are known as interval graphs) and covering the complement of the graph by co-interval graphs (a co-interval graph is the complement of an interval graph).

Many graphs arising in practice can be represented in a concise and intuitive way that conveys their structure. For example: A planar graph can be represented in the plane with points for vertices and non-crossing curves for edges. An interval graph can be represented on the real line with intervals for vertices and intersection of intervals representing edges. The concept of ``simultaneity'' applies for several types of graphs: the idea is to find representations for two graphs that share some common vertices and edges, and ensure that the common vertices and edges are represented the same way. Simultaneous representation problems arise in any situation where two related graphs should be represented consistently. A main instance is for temporal relationships, where an old graph and a new graph share some common parts. Pairs of related graphs arise in many other situations. For example, two social networks that share some members; two schedules that share some events, overlap graphs of DNA fragments of two similar organisms, circuit graphs of two adjacent layers on a computer chip etc. In this thesis, we study the simultaneous representation problem for several graph classes. For planar graphs the problem is defined as follows. Let G1 and G2 be two graphs sharing some vertices and edges. The simultaneous planar embedding problem asks whether there exist planar embeddings (or drawings) for G1 and G2 such that every vertex shared by the two graphs is mapped to the same point and every shared edge is mapped to the same curve in both embeddings. Over the last few years there has been a lot of work on simultaneous planar embeddings, which have been called `simultaneous embeddings with fixed edges'. A major open question is whether simultaneous planarity for two graphs can be tested in polynomial time. We give a linear-time algorithm for testing the simultaneous planarity of any two graphs that share a 2-connected subgraph. Our algorithm also extends to the case of k planar graphs, where each vertex [edge] is either common to all graphs or belongs to exactly one of them. Next we introduce a new notion of simultaneity for intersection graph classes (interval graphs, chordal graphs etc.) and for comparability graphs. For interval graphs, the problem is defined as follows. Let G1 and G2 be two interval graphs sharing some vertices I and the edges induced by I. G1 and G2 are said to be `simultaneous interval graphs' if there exist interval representations of G1 and G2 such that any vertex of I is assigned to the same interval in both the representations. The `simultaneous representation problem' for interval graphs asks whether G1 and G2 are simultaneous interval graphs. The problem is defined in a similar way for other intersection graph classes. For comparability graphs and any intersection graph class, we show that the simultaneous representation problem for the graph class is equivalent to a graph augmentation problem: given graphs G1 and G2, sharing vertices I and the corresponding induced edges, do there exist edges E' between G1-I and G2-I such that the graph G1 U G_2 U E' belongs to the graph class. This equivalence implies that the simultaneous representation problem is closely related to other well-studied classes in the literature, namely, sandwich graphs and probe graphs. We give efficient algorithms for solving the simultaneous representation problem for interval graphs, chordal graphs, comparability graphs and permutation graphs. Further, our algorithms for comparability and permutation graphs solve a more general version of the problem when there are multiple graphs, any two of which share the same common graph. This version of the problem also generalizes probe graphs.

Many graphs arising in practice can be represented in a concise and intuitive way that conveys their structure. For example: A planar graph can be represented in the plane with points for vertices and non-crossing curves for edges. An interval graph can be represented on the real line with intervals for vertices and intersection of intervals representing edges. The concept of ``simultaneity'' applies for several types of graphs: the idea is to find representations for two graphs that share some common vertices and edges, and ensure that the common vertices and edges are represented the same way. Simultaneous representation problems arise in any situation where two related graphs should be represented consistently. A main instance is for temporal relationships, where an old graph and a new graph share some common parts. Pairs of related graphs arise in many other situations. For example, two social networks that share some members; two schedules that share some events, overlap graphs of DNA fragments of two similar organisms, circuit graphs of two adjacent layers on a computer chip etc. In this thesis, we study the simultaneous representation problem for several graph classes. For planar graphs the problem is defined as follows. Let G1 and G2 be two graphs sharing some vertices and edges. The simultaneous planar embedding problem asks whether there exist planar embeddings (or drawings) for G1 and G2 such that every vertex shared by the two graphs is mapped to the same point and every shared edge is mapped to the same curve in both embeddings. Over the last few years there has been a lot of work on simultaneous planar embeddings, which have been called `simultaneous embeddings with fixed edges'. A major open question is whether simultaneous planarity for two graphs can be tested in polynomial time. We give a linear-time algorithm for testing the simultaneous planarity of any two graphs that share a 2-connected subgraph. Our algorithm also extends to the case of k planar graphs, where each vertex [edge] is either common to all graphs or belongs to exactly one of them. Next we introduce a new notion of simultaneity for intersection graph classes (interval graphs, chordal graphs etc.) and for comparability graphs. For interval graphs, the problem is defined as follows. Let G1 and G2 be two interval graphs sharing some vertices I and the edges induced by I. G1 and G2 are said to be `simultaneous interval graphs' if there exist interval representations of G1 and G2 such that any vertex of I is assigned to the same interval in both the representations. The `simultaneous representation problem' for interval graphs asks whether G1 and G2 are simultaneous interval graphs. The problem is defined in a similar way for other intersection graph classes. For comparability graphs and any intersection graph class, we show that the simultaneous representation problem for the graph class is equivalent to a graph augmentation problem: given graphs G1 and G2, sharing vertices I and the corresponding induced edges, do there exist edges E' between G1-I and G2-I such that the graph G1 U G_2 U E' belongs to the graph class. This equivalence implies that the simultaneous representation problem is closely related to other well-studied classes in the literature, namely, sandwich graphs and probe graphs. We give efficient algorithms for solving the simultaneous representation problem for interval graphs, chordal graphs, comparability graphs and permutation graphs. Further, our algorithms for comparability and permutation graphs solve a more general version of the problem when there are multiple graphs, any two of which share the same common graph. This version of the problem also generalizes probe graphs.

Interval graphs are well studied structures. Intervals can represent resources like jobs to be sched-uled. Finding maximum independent set in interval graphs would correspond to scheduling maximum number of non-conflicting jobs on the computer. Most optimization problems on interval graphs like independent set, vertex cover, dominating set, maximum clique, etc can be solved efficiently using combinatorial algorithms in polynomial time. Hitting, Covering and Packing problems have been ex-tensively studied in the last few decades and have applications in diverse areas. While they are NP-hard for most settings, they are polynomial solvable for intervals. In this thesis, we consider the generaliza-tions of hitting, covering and packing problems for intervals. We model these problems as min-cost flow problems using non-trivial reduction and solve it using standard flow algorithms. Demand-hitting problem which is a generalization of hitting problem is defined as follows: Given N intervals, a positive integer demand for every interval, M points, a real weight for every point, select a subset of points H, such that every interval contains at least as many points in H as its demand and sum of weight of the points in H is minimized. Note that if the demand is one for all intervals, we get the standard hitting set problem. In this case, we give a dynamic programming based O(M + N) time algorithm assuming that intervals and points are sorted. A special case of the demand-hitting set is the K-hitting set problem where the demand of all the intervals is K. For the K-hitting set problem, we give a O(M2N) time flow based algorithm. For the demand-hitting problem, we make an assumption that no interval is contained in another interval. Under this assumption, we give a O(M2N) time flow based algorithm. Demand-covering problem which is a generalization of covering problem is defined as follows: Given N intervals, a real weight for every interval, M points, a positive integer demand for every point, select a subset of intervals C, such that every point is contained in at least as many intervals in C as its demand and sum of weight of the intervals in C is minimized. Note that if the demand of points are one, we get the standard covering set problem. In this case, we give a dynamic programming based O(M + N log N) time algorithm assuming that points are sorted. A special case of the demand-covering set is the K-covering set problem where the demand of all the points is K. For the K-covering set problem, we give a O(MN2) time flow based algorithm. For the demand-covering problem, we give a O(MN2) time flow based algorithm. K-pack points problem which is a generalization of packing problem is defined as follows: Given N intervals, an integer K, M points, a real weight for every point, select a subset of points Y , such that every interval contains at most K points from Y and sum of weight of the points in Y is maximized. Note that if K is one, we get the standard pack points problem. In this case, we give a dynamic pro-gramming based O(M + N) time algorithm assuming that points and intervals are sorted. For K-pack points problem, we give O(M2 log M) time flow based algorithm assuming that intervals and points are sorted.