INVESTIGADORES
LIN Min Chih
congresos y reuniones científicas
Título:
Proper Helly Circular-Arc Graphs
Autor/es:
MIN CHIH LIN; FRANCISCO J. SOULIGNAC; JAYME L. SZWARCFITER
Lugar:
Dornburg, Alemania
Reunión:
Conferencia; WG'07 (33rd International Workshop on Graph-Theoretic Concepts in Computer Science); 2007
Institución organizadora:
Universität Rostock, Germany
Resumen:
A circular-arc model
is a circle C together with a collection
of arcs of C. If no arc is contained in any other then
is a proper circular-arc model, if every arc has the same length then
is a unit circular-arc model and if
satisfies the Helly Property then
is a Helly circular-arc model. A (proper) (unit) (Helly) circular-arc
graph is the intersection graph of the arcs of a (proper) (Helly)
circular-arc model. Circular-arc graphs and their subclasses have been
the object of a great deal of attention in the literature. Linear time
recognition algorithms have been described both for the general class
and for some of its subclasses. In this article we study the
circular-arc graphs which admit a model which is simultaneously proper
and Helly. We describe characterizations for this class, including one
by forbidden induced subgraphs. These characterizations lead to linear
time certifying algorithms for recognizing such graphs. Furthermore, we
extend the results to graphs which admit a model which is
simultaneously unit and Helly, also leading to characterizations and a
linear time certifying algorithm.