Problems on bend-number, circular separation dimension and maximum edge 2-colouring

Abstract

Representation of graphs as the intersection graphs of geometric objects has a long history. The objective is to a nd a collection of \simple" sets S such that a given graph G is its intersection graph. We are interested in two types of intersection representations motivated by VLSI circuit layout problem. In these models, vertices are represented by polygonal paths with alternating horizontal and vertical segments. The measure of the complexity of a path is de fined by the number of bends it has. The objective is to minimise the maximum number of bends used by any path in a representation. This minimum number (over all possible representations) is called the bend number of the graph. In the first model, two vertices share an edge if and only if corresponding paths intersect. A graph that can be represented in such a way is called a VPG graph. We study a subclass of the planar graphs on this model. In the second model, two vertices of the graph share an edge if and only if corresponding paths overlap on a non-zero length segment. A graph that can be represented in such a way is called an EPG graph. We study Halin graphs which is a subclass of the planar graphs, fully subdivided graphs and minimally 2-connected graphs for this model. Using one of these results, we show optimization problems such as maximum independent set, minimum dominating set are APX-hard on 1-bend EPG graphs. We devise a polynomial time algorithm for the colouring and maximum independent set problem on two-sided boundary generated EPG graphs which is a subclass of 1-bend EPG graphs. We also establish NP-hardness and inapproximability result on three-sided boundary generated EPG graphs and four-sided boundary generated EPG graphs. In the second part, we study the notion of circular separation dimension which was introduced recently by Douglas West. Formally, a pair of non-adjacent edges is said to be separated in a circular ordering of vertices if the endpoints of the two edges do not alternate in the ordering. The circular separation dimension (CSD) of a graph G is the minimum number of circular orderings of the vertices of G such that every pair of non-adjacent edges is separated in at least one of the circular orderings. We establish a new upper bound for CSD in terms of the chromatic number of the graph. We further study this question for special graph classes such as series-parallel graphs and two-outerplanar graphs. In the nal part, we study maximum edge 2-colouring problem. For a graph G, the maximum edge 2-colouring problem seeks the maximum possible colours that can be used to colour the edges of the graph such that edges incident on a vertex span at most two distinct colours. The problem is well studied in combinatorics, in the context of the anti-Ramsey number. Algorithmically, the problem is known to be NP-hard. It is also known that no polynomial time algorithm can approximate to a factor less than 3=2 assuming the unique game conjecture. The obvious but the only known algorithm issues different colours to the edges of a maximum matching and different colours to remaining connected components. We establish an improved approximation bound of 8=5 for the algorithm, for triangle-free graphs with perfect matching.