Institute of Computer Science III
University of Bonn
Databases * Information Systems * Software Engineering *
Pattern Recognition * Image Processing * Artificial Intelligence * Robotics
Extended circle graphs I
Christoph Hundack and Hermann Stamm-Wilbrandt
A graph C is called an extended circle graph if it is the intersection graph of a finite set of hyperchords of a circle. A hyperchord is defined by the interior of a polygon which is given by a finite, ordered set H of points on a circle. (We assume the selected points on the circle to be numbered consecutively from 1 to n.) The class of extended circle graphs is a generalization of a number of well-known graph classes, eg circle graphs and trapezoid graphs and it is known under various names. We summarize a number of results concerning class inclusions, related graph models, and algorithms for extended circle graphs.
We introduce an efficient description for these graphs which is linear in the input size I = PH2V (C) jHj, although C may contain \Theta (I2) edges. This permits algorithms with running time sublinear in jV (C)j + jE(C)j; as an example we present a bipartation algorithm for extended circle graphs.
Click here to obtain the full paper (PS, gzip, 66685 bytes, 17 pages)
webmaster@www.informatik.uni-bonn.de -
16.12.05