Circular-arc graph

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.

A circular-arc graph (left) and a corresponding arc model (right).

Formally, let

${\displaystyle I_{1},I_{2},\ldots ,I_{n}\subset C_{1}}$

be a set of arcs. Then the corresponding circular-arc graph is G = (V, E) where

${\displaystyle V=\{I_{1},I_{2},\ldots ,I_{n}\}}$

and

${\displaystyle \{I_{\alpha },I_{\beta }\}\in E\iff I_{\alpha }\cap I_{\beta }\neq \varnothing .}$

A family of arcs that corresponds to G is called an arc model.

Recognition

Tucker (1980) demonstrated the first polynomial recognition algorithm for circular-arc graphs, which runs in ${\displaystyle {\mathcal {O}}(n^{3})}$ time. McConnell (2003) gave the first linear ${\displaystyle ({\mathcal {O}}(n+m))}$ time recognition algorithm, where ${\displaystyle m}$ is the number of edges. More recently, Kaplan and Nussbaum^[1] developed a simpler linear time recognition algorithm.

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 C₅, C₇, etc., are circular-arc graphs.

Some subclasses

In the following, let ${\displaystyle G=(V,E)}$ be an arbitrary graph.

Unit circular-arc graphs

${\displaystyle G}$ is a unit circular-arc graph if there exists a corresponding arc model such that each arc is of equal length.

The number of labelled unit circular-arc graphs on n vertices is given by ${\displaystyle (n+2){\binom {2n-1}{n-1}}-2^{2n-1}}$. ^[2]

Proper circular-arc graphs

${\displaystyle G}$ is a proper circular-arc graph (also known as a circular interval graph)^[3] 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 ${\displaystyle ({\mathcal {O}}(n+m))}$ time.^[4] They form one of the fundamental subclasses of the claw-free graphs.^[3]

Helly circular-arc graphs

${\displaystyle 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 ${\displaystyle {{\mathcal {O}}(n^{3})}}$ recognition algorithm.

Joeris et al. (2009) give other characterizations of this class, which imply a recognition algorithm that runs in O(n+m) time when the input is a graph. If the input graph is not a Helly circular-arc graph, then the algorithm returns a certificate of this fact in the form of a forbidden induced subgraph. They also gave an O(n) time algorithm for determining whether a given circular-arc model has the Helly property.

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.

Notes

1. Kaplan, Haim; Nussbaum, Yahav (2011-11-01). "A Simpler Linear-Time Recognition of Circular-Arc Graphs". Algorithmica. 61 (3): 694–737. CiteSeerX 10.1.1.76.2480. doi:10.1007/s00453-010-9432-y. ISSN 0178-4617.
2. Alexandersson, Per; Panova, Greta (December 2018). "LLT polynomials, chromatic quasisymmetric functions and graphs with cycles". Discrete Mathematics. 341 (12): 3453–3482. arXiv:1705.10353. doi:10.1016/j.disc.2018.09.001.
3. Described with a different but equivalent definition by Chudnovsky & Seymour (2008).
4. Deng, Hell & Huang (1996) pg. ?

References

• Chudnovsky, Maria; Seymour, Paul (2008), "Claw-free graphs. III. Circular interval graphs" (PDF), Journal of Combinatorial Theory, Series B, 98 (4): 812–834, doi:10.1016/j.jctb.2008.03.001, MR 2418774.
• Deng, Xiaotie; Hell, Pavol; Huang, Jing (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.
• Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, ISBN 978-0-444-51530-8, archived from the original on 2010-05-22, retrieved 2008-05-21. Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004.
• Joeris, Benson L.; Lin, Min Chih; McConnell, Ross M.; Spinrad, Jeremy P.; Szwarcfiter, Jayme L. (2009), "Linear-Time Recognition of Helly Circular-Arc Models and Graphs", Algorithmica, 59 (2): 215–239, CiteSeerX 10.1.1.298.3038, doi:10.1007/s00453-009-9304-5.
• McConnell, Ross (2003), "Linear-time recognition of circular-arc graphs", Algorithmica, 37 (2): 93–147, CiteSeerX 10.1.1.22.4725, doi:10.1007/s00453-003-1032-7.
• Tucker, Alan (1980), "An efficient test for circular-arc graphs", SIAM Journal on Computing, 9 (1): 1–24, doi:10.1137/0209001.

External links

• Circular arc graph, Information System on Graph Class Inclusions