Algorithmic and Combinatorial Questions on Some Geometric Problems on Graphs
Abstract
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 geometric representations of graphs in higher dimensions. Both these parameters are known to be NPHard 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 eﬃcient 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 sublinear factor approximation algorithm known for computing the boxicity and cubicity of general graphs.
Planar griddrawings 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 eﬃcient algorithm to 2vertexconnect 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 griddrawings of outerplanar graphs, extending the existing algorithm known for 2vertex connected outerplanar graphs.
n−1
3
Maximum matchings in triangle distance Delaunay graphs: Delaunay 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 Triangle Distance Delaunay graph. TDDelaunay 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 nondegenerate 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 colored 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 heterochromatic path in an edgecolored 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 fourcycles 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, trianglefree graphs and graphs without heterochromatic triangles.
Collections
Related items
Showing items related by title, author, creator and subject.

Rainbow Colouring and Some Dimensional Problems in Graph Theory
Rajendraprasad, Deepak (20180405)This thesis touches three diﬀerent topics in graph theory, namely, rainbow colouring, product dimension and boxicity. Rainbow colouring An edge colouring of a graph is called a rainbow colouring, if every pair of vertices ... 
Rainbow Connection Number Of Graph Power And Graph Products
Arunselvan, R (20140909)The minimum number of colors required to color the edges of a graph so that any two distinct vertices are connected by at least one path in which no two edges are colored the same is called its rainbow connection number. ... 
Intersection Graphs Of Boxes And Cubes
Francis, Mathew C (20110125)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 ...