Circular-arc graph
From Wikipedia, the free encyclopedia
In graph theory, a circular-arc graph is the intersection graph of a set of arcs on the circle. It has one vertex for each arc in the set, and an edge between every pair of vertices corresponding to arcs that intersect.
Formally, let
be a set of arcs. Then the corresponding circular-arc graph is G = (V, E) where
and
A family of arcs that corresponds to G is called an arc model.
Contents |
[edit] Recognition
Tucker (1980) demonstrated the first polynomial recognition algorithm for circular-arc graphs, which runs in time. More recently, McConnell (2003) gave the first linear time recognition algorithm.
[edit] Relation to other graph classes
Circular-arc graphs are a natural generalization of interval graphs. If a circular-arc graph G has an arc model that leaves some point of the circle uncovered, the circle can be cut at that point and stretched to a line, which results in an interval representation. Unlike interval graphs, however, circular-arc graphs are not always perfect, as the odd chordless cycles C5, C7, etc., are circular-arc graphs.
[edit] Some subclasses
In the following, let G = (V,E) be an arbitrary graph.
[edit] Unit circular-arc graphs
G is a unit circular-arc graph if there exists a corresponding arc model such that each arc is of equal length.
[edit] Proper circular-arc graphs
G is a proper circular-arc graph if there exists a corresponding arc model such that no arc properly contains another. Recognizing these graphs and constructing a proper arc model can both be performed in linear time.[1]
[edit] Helly circular-arc graphs
G is a Helly circular-arc graph if there exists a corresponding arc model such that the arcs constitute a Helly family. Gavril (1974) gives a characterization of this class that implies an recognition algorithm.
[edit] Applications
Circular-arc graphs are useful in modeling periodic resource allocation problems in operations research. Each interval represents a request for a resource for a specific period repeated in time.
[edit] Notes
[edit] References
- Tucker, Alan (1980), “An efficient test for circular-arc graphs”, SIAM Journal on Computing 9 (1): 1–24, DOI 10.1137/0209001.
- McConnell, Ross (2003), “Linear-time recognition of circular-arc graphs”, Algorithmica 37 (2): 93–147, DOI 10.1007/s00453-003-1032-7
- Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, ISBN 0-444-51530-5, <http://www.elsevier.com/wps/find/bookdescription.cws_home/699916/description#description> Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004.
- Deng, Xiaotie & Huang, Pavol (1996), “Linear-Time representation algorithms for proper circular-arc graphs and proper interval graphs”, SIAM Journal on Computing 25 (2): 390–403, DOI 10.1137/S0097539792269095.
- Gavril, Fanica (1974), “Algorithms on circular-arc graphs”, Networks 4 (4): 357–369, DOI 10.1002/net.3230040407