2-connected outerplanar graphs have a unique minimal cycle basis with length 2|E|-|V|. They are the only Hamiltonian graphs with a cycle basis of this length. (author's abstract) / Series: Preprint Series / Department of Applied Statistics and Data Processing

This thesis examines a wide collection of frequency assignment problems. One of the largest topics in this thesis is that of L(2,1)-labellings of outerplanar graphs. The main result in this topic is the fact that there exists a polynomial time algorithm to determine the minimum L(2,1)-span for an outerplanar graph. This result generalises the analogous result for trees, solves a stated open problem and complements the fact that the problem is NP-complete for planar graphs. We furthermore give best possible bounds on the minimum L(2,1)-span and the cyclic-L(2,1)-span in outerplanar graphs, when the maximum degree is at least eight. We also give polynomial time algorithms for solving the standard constraint matrix problem for several classes of graphs, such as chains of triangles, the wheel and a larger class of graphs containing the wheel. We furthermore introduce the concept of one-close-neighbour problems, which have some practical applications. We prove optimal results for bipartite graphs, odd cycles and complete multipartite graphs. Finally we evaluate different algorithms for the frequency assignment problem, using domination analysis. We compute bounds for the domination number of some heuristics for both the fixed spectrum version of the frequency assignment problem and the minimum span frequency assignment problem. Our results show that the standard greedy algorithm does not perform well, compared to some slightly more advanced algorithms, which is what we would expect. In this thesis we furthermore give some background and motivation for the topics being investigated, as well as mentioning several open problems.

O tema central deste trabalho é o estudo de problemas sobre caminhos mais longos em grafos, de pontos de vista tanto estrutural como algorítmico. A primeira parte tem como foco o estudo de problemas motivados pela seguinte questão levantada por T. Gallai em 1966: é verdade que em todo grafo conexo existe um vértice comum a todos os seus caminhos mais longos? Hoje, já se conhecem diversos grafos conexos cuja intersecção de todos os seus caminhos mais longos é vazia. Entretanto, existem classes de grafos para as quais a resposta à pergunta de Gallai é afirmativa. Nessa linha, apresentamos alguns resultados da literatura e duas novas classes que obtivemos: os grafos exoplanares e as 2-árvores. Motivado por esse problema, nos anos 80, T. Zamfirescu formulou a seguinte pergunta que permanece em aberto: é verdade que em todo grafo conexo existe um vértice comum a quaisquer três de seus caminhos mais longos? Apresentamos, além de alguns resultados conhecidos, uma prova de que a resposta é afirmativa para grafos em que todo bloco não trivial é hamiltoniano. Notamos que esse último resultado e o acima mencionado para grafos exoplanares generalizam um teorema de M. Axenovich (2009) que afirma que quaisquer três caminhos mais longos em um grafo exoplanar têm um vértice em comum. Finalmente, mencionamos alguns outros resultados da literatura relacionados com o tema. Na segunda parte, investigamos o problema de encontrar um caminho mais longo em um grafo. Este problema é NP-difícil para grafos arbitrários. Isto motiva investigações em duas linhas a respeito da busca de tais caminhos. Pode-se procurar classes especiais de grafos para as quais existem algoritmos polinomiais, ou pode-se abrir mão da busca de um caminho mais longo, e projetar um algoritmo eficiente que encontra um caminho cujo comprimento esteja próximo do comprimento de um mais longo. Nesse trabalho estudamos ambas as abordagens e apresentamos alguns resultados da literatura. / The central theme of this thesis is the study of problems related to longest paths in graphs, both from a structural and an algorithmic point of view. The first part focuses on the study of problems motivated by the following question raised by T. Gallai in 1966: is it true that every connected graph has a vertex common to all its longest paths? Today, many connected graphs in which all longest paths have empty intersection are known. However, there are classes of graphs for which Gallais question has a positive answer. In this direction, we present some results from the literature, as well as two new classes we obtained: outerplanar graphs and 2-trees. Motivated by this problem, T. Zamfirescu, in the 80s, proposed the following question which remains open: is it true that every connected graph has a vertex common to any three of its longest paths? We present, in addition to some known results, a proof that the answer to this question is positive for graphs in which all non-trivial blocks are Hamiltonian. We note that this result and the one mentioned above for outerplanar graphs generalize a theorem of M. Axenovich (2009) that states that any three longest paths in an outerplanar graph have a common vertex. Finally, we mention some other related results from the literature. In the second part, we investigate the problem of finding a longest path in a graph. This problem is NP-hard for arbitrary graphs. This motivates investigations in two directions with respect to the search for such paths. We can look for special classes of graphs for which the problem is polynomially solvable, or we can relinquish the search for a longest path and design an efficient algorithm that finds a path whose length is close to that of a longest path. In this thesis we study both approaches and present some results from the literature.

在這篇論文中，我們針對2-連通的最大外平面圖而且是二分圖的圖形，討論 其容忍表示法，並找到它的所有禁止子圖H1、H2、H3、H4。 / In this thesis, we prove a 2-connected graph G which is maximal outerplanar and bipartite is a tolerance graph if and only if there is no induced subgraphs H1; H2; H3 and H4 of G.

O tema central deste trabalho é o estudo de problemas sobre caminhos mais longos em grafos, de pontos de vista tanto estrutural como algorítmico. A primeira parte tem como foco o estudo de problemas motivados pela seguinte questão levantada por T. Gallai em 1966: é verdade que em todo grafo conexo existe um vértice comum a todos os seus caminhos mais longos? Hoje, já se conhecem diversos grafos conexos cuja intersecção de todos os seus caminhos mais longos é vazia. Entretanto, existem classes de grafos para as quais a resposta à pergunta de Gallai é afirmativa. Nessa linha, apresentamos alguns resultados da literatura e duas novas classes que obtivemos: os grafos exoplanares e as 2-árvores. Motivado por esse problema, nos anos 80, T. Zamfirescu formulou a seguinte pergunta que permanece em aberto: é verdade que em todo grafo conexo existe um vértice comum a quaisquer três de seus caminhos mais longos? Apresentamos, além de alguns resultados conhecidos, uma prova de que a resposta é afirmativa para grafos em que todo bloco não trivial é hamiltoniano. Notamos que esse último resultado e o acima mencionado para grafos exoplanares generalizam um teorema de M. Axenovich (2009) que afirma que quaisquer três caminhos mais longos em um grafo exoplanar têm um vértice em comum. Finalmente, mencionamos alguns outros resultados da literatura relacionados com o tema. Na segunda parte, investigamos o problema de encontrar um caminho mais longo em um grafo. Este problema é NP-difícil para grafos arbitrários. Isto motiva investigações em duas linhas a respeito da busca de tais caminhos. Pode-se procurar classes especiais de grafos para as quais existem algoritmos polinomiais, ou pode-se abrir mão da busca de um caminho mais longo, e projetar um algoritmo eficiente que encontra um caminho cujo comprimento esteja próximo do comprimento de um mais longo. Nesse trabalho estudamos ambas as abordagens e apresentamos alguns resultados da literatura. / The central theme of this thesis is the study of problems related to longest paths in graphs, both from a structural and an algorithmic point of view. The first part focuses on the study of problems motivated by the following question raised by T. Gallai in 1966: is it true that every connected graph has a vertex common to all its longest paths? Today, many connected graphs in which all longest paths have empty intersection are known. However, there are classes of graphs for which Gallais question has a positive answer. In this direction, we present some results from the literature, as well as two new classes we obtained: outerplanar graphs and 2-trees. Motivated by this problem, T. Zamfirescu, in the 80s, proposed the following question which remains open: is it true that every connected graph has a vertex common to any three of its longest paths? We present, in addition to some known results, a proof that the answer to this question is positive for graphs in which all non-trivial blocks are Hamiltonian. We note that this result and the one mentioned above for outerplanar graphs generalize a theorem of M. Axenovich (2009) that states that any three longest paths in an outerplanar graph have a common vertex. Finally, we mention some other related results from the literature. In the second part, we investigate the problem of finding a longest path in a graph. This problem is NP-hard for arbitrary graphs. This motivates investigations in two directions with respect to the search for such paths. We can look for special classes of graphs for which the problem is polynomially solvable, or we can relinquish the search for a longest path and design an efficient algorithm that finds a path whose length is close to that of a longest path. In this thesis we study both approaches and present some results from the literature.

本文針對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.

This thesis mainly focuses on algorithmic and combinatorial questions related to some geometric problems on graphs. In the last part of this thesis, a graph coloring problem is also discussed. Boxicity and Cubicity: These are graph parameters dealing with geomet-ric representations of graphs in higher dimensions. Both these parameters are known to be NP-Hard to compute in general and are even hard to approximate within an O(n1− ) factor for any > 0, under standard complexity theoretic assumptions. We studied algorithmic questions for these problems, for certain graph classes, to yield efficient algorithms or approximations. Our results include a polynomial time constant factor approximation algorithm for computing the cubicity of trees and a polynomial time constant (≤ 2.5) factor approximation algorithm for computing the boxicity of circular arc graphs. As far as we know, there were no constant factor approximation algorithms known previously, for computing boxicity or cubicity of any well known graph class for which the respective parameter value is unbounded. We also obtained parameterized approximation algorithms for boxicity with various edit distance parameters. An o(n) factor approximation algorithm for computing the boxicity and cubicity of general graphs also evolved as an interesting corollary of one of these parameterized algorithms. This seems to be the first sub-linear factor approximation algorithm known for computing the boxicity and cubicity of general graphs. Planar grid-drawings of outerplanar graphs: A graph is outerplanar, if it has a planar embedding with all its vertices lying on the outer face. We give an efficient algorithm to 2-vertex-connect any connected outerplanar graph G by adding more edges to it, in order to obtain a supergraph of G such that the resultant graph is still outerplanar and its pathwidth is within a constant times the pathwidth of G. This algorithm leads to a constant factor approximation algorithm for computing minimum height planar straight line grid-drawings of outerplanar graphs, extending the existing algorithm known for 2-vertex connected outerplanar graphs. n−1 3 Maximum matchings in triangle distance Delaunay graphs: Delau-nay graphs of point sets are well studied in Computational Geometry. Instead of the Euclidean metric, if the Delaunay graph is defined with respect to the convex distance function defined by an equilateral triangle, it is called a Trian-gle Distance Delaunay graph. TD-Delaunay graphs are known to be equivalent to geometric spanners called half-Θ6 graphs. It is known that classical Delaunay graphs of point sets always contain a near perfect matching, for non-degenerate point sets. We show that Triangle Distance Delaunay graphs of a set of n points in general position will always l m contain a matching of size and this bound is tight. We also show that Θ6 graphs, a class of supergraphs of half-Θ6 graphs, can have at most 5n − 11 edges, for point sets in general position. Heterochromatic Paths in Edge Colored Graphs: Conditions on the coloring to guarantee the existence of long heterochromatic paths in edge col-ored graphs is a well explored problem in literature. The objective here is to obtain a good lower bound for λ(G) - the length of a maximum heterochro-matic path in an edge-colored graph G, in terms of ϑ(G) - the minimum color degree of G under the given coloring. There are graph families for which λ(G) = ϑ(G) − 1 under certain colorings, and it is conjectured that ϑ(G) − 1 is a tight lower bound for λ(G). We show that if G has girth is at least 4 log2(ϑ(G))+2, then λ(G) ≥ ϑ(G)− 2. It is also proved that a weaker requirement that G just does not contain four-cycles is enough to guarantee that λ(G) is at least ϑ(G) −o(ϑ(G)). Other special cases considered include lower bounds for λ(G) in edge colored bipartite graphs, triangle-free graphs and graphs without heterochromatic triangles.