Computer Science – Discrete Mathematics
Scientific paper
2011-03-18
Computer Science
Discrete Mathematics
39 pages, 13 figures. A previous version of the paper (entitled Proper Helly Circular-Arc Graphs) appeared at WG'07
Scientific paper
A Helly circular-arc model M = (C,A) is a circle C together with a Helly family \A of arcs of C. If no arc is contained in any other, then M is a proper Helly circular-arc model, if every arc has the same length, then M is a unit Helly circular-arc model, and if there are no two arcs covering the circle, then M is a normal Helly circular-arc model. A Helly (resp. proper Helly, unit Helly, normal Helly) circular-arc graph is the intersection graph of the arcs of a Helly (resp. proper Helly, unit Helly, normal Helly) circular-arc model. In this article we study these subclasses of Helly circular-arc graphs. We show natural generalizations of several properties of (proper) interval graphs that hold for some of these Helly circular-arc subclasses. Next, we describe characterizations for the subclasses of Helly circular-arc graphs, including forbidden induced subgraphs characterizations. These characterizations lead to efficient algorithms for recognizing graphs within these classes. Finally, we show how do these classes of graphs relate with straight and round digraphs.
Lin Min Chih
Soulignac Francisco J.
Szwarcfiter Jayme L.
No associations
LandOfFree
Subclasses of Normal Helly Circular-Arc Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Subclasses of Normal Helly Circular-Arc Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Subclasses of Normal Helly Circular-Arc Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-198388