An algorithm for a maximum clique of the intersection graph of isooriented rectangles on a cylinder
Takashi Kizu, Toshiro Araki, Toshinobu Kashiwabara · Electronics and Communications in Japan (Part III Fundamental Electronic Science) · 1996
Abstract A set ℱ of rectangles is considered which are placed on the surface of a right cylinder such that two of their sides are parallel to the axis of the cylinder. A graph G = (V, E) is called a rectangle‐on‐a‐cylinder‐intersection graph with a model ℱ, if the vertices of G can be put into a one‐to‐one correspondence with the rectangles in ℱ, such that two rectangles in ℱ have nonempty intersection if and only if two vertices corresponding to them are connected by an edge in G. In this paper, it is shown that given an ℱ, a maximum clique of the corresponding rectangle‐on‐a‐cylinder‐intersection graph can be obtained in polynomial time, by repeatedly using an algorithm for finding a maximum clique of a circular‐arc graph. Furthermore, an algorithm is constructed which, given a dynamic set C (initially empty) of circular arcs which changes as arcs are added to or deleted from C, finds a maximum clique of the circulararc graph corresponding to C in O(m(d + 1)) time every time C is changed (here m is the number of arcs and d is the number of arcs intersecting the added or deleted arc). It is also shown that, using this algorithm, an algorithm can be constructed for finding a maximum clique of a rectangle‐on‐a‐cylinder‐intersection graph in O(n(n + e)) time (n is the number of vertices and e is the number of edges).