Graphclass: circular arc

Definition:

A circular arc graph is the intersection graph of arcs of a circle.

Open problems

  1. Characterize circular arc graphs by forbidden induced subgraphs
    [1404]
    M.C. Lin, J.L. Szwarcfiter
    Characterizations and recognition of circular-arc graphs and subclasses: A survey
    Discrete Math. 309 No.18, 5618-5635 (2009)
    .
  2. Give an algorithm for finding a certificate for a graph not to be a circular arc graph
    [1404]
    M.C. Lin, J.L. Szwarcfiter
    Characterizations and recognition of circular-arc graphs and subclasses: A survey
    Discrete Math. 309 No.18, 5618-5635 (2009)
    .
  3. Characterize circular arc graphs that admit a model where the arcs have to most two sizes
    [1404]
    M.C. Lin, J.L. Szwarcfiter
    Characterizations and recognition of circular-arc graphs and subclasses: A survey
    Discrete Math. 309 No.18, 5618-5635 (2009)
    .
  4. Characterize circular arc bigraphs (see interval bigraph )
    [1404]
    M.C. Lin, J.L. Szwarcfiter
    Characterizations and recognition of circular-arc graphs and subclasses: A survey
    Discrete Math. 309 No.18, 5618-5635 (2009)
    .

References

[453]
M.C. Golumbic
Algorithmic Graph Theory and Perfect Graphs
Academic Press, New York 1980
[777]
T.A. McKee, F.R. McMorris
Topics in Intersection Graph Theory
SIAM Monographs on Discrete Mathematics. and Applications, 2. Philadelphia, PA: SIAM, Society for Industrial and Applied Mathematics. viii, 205 p. (1999). [ISBN 0-89871-430-3]
[1037]
A.C. Tucker
Matrix characterizations of circular--arc graphs
Pacific J. Math. 39 1971 535--545
[1038]
A.C. Tucker
A structure theorem for the consecutive 1's property
J. Comb. Theory 12 1972 153--162
[1043]
A.C. Tucker
An efficient test for circular--arc graphs
SIAM J. Computing 9 1980 1--24
[1404]
M.C. Lin, J.L. Szwarcfiter
Characterizations and recognition of circular-arc graphs and subclasses: A survey
Discrete Math. 309 No.18, 5618-5635 (2009)

;

[119]
H.L. Bodlaender
A tourist guide through treewidth
Acta Cybernetica 11 1993 1--23
[995]
J.P. Spinrad
Efficient graph representations
American Mathematical Society, Fields Institute Monograph Series 19 (2003)
[1105]
M.C. Golumbic, P.L Hammer
Stability in circular arc graphs.
J. Algorithms 9 (1988) 56-63
[1106]
W.L. Hsu, J.P. Spinrad
Independent sets in circular arc graphs
J. Algorithms 19 (1995) 145-160
[1143]
M.S. Chang
Efficient algorithms for the domination problems on interval and circular-arc graphs.
SIAM J. Comput. 27, No.6, 1671-1694 (1998)
[1158]
Hsu, Wen-Lian; Tsai, Kuo-Hui
Linear time algorithms on circular-arc graphs.
Inf. Process. Lett. 40, No.3, 123-129 (1991)
[1219]
R. McConnell
Linear-time recognition of circular-arc graphs.
Algorithmica 37 (2003) 93-47
[1429]
W.-L. Hsu
Maximum weight clique algorithms for circular-arc graphs and circle graphs
SIAM J. Computing 14 No.1 224-231 (1985)
[1438]
M.R. Garey, D.S. Johnson, G.L. Miller, C.H. Papadimitriou
The complexity of coloring circular arcs and chords
SIAM J. on Algebraic and Discrete Methods 1 No.2 216-227 (1980)
[1527]
W.K. Shih, T.C. Chen, W.L. Hsu
An O(n^2 log n) algorithm for the Hamiltonian cycle problem on circular-arc graphs
SIAM J. Comput. 21 No.6 1026-1046 (1992)
[1536]
R.-W. Hung, M.-S. Chang, C.-H. Laio
The Hamiltonian cycle problem on circular-arc graphs
Proc. of the International MultiConference of Engineers and Computer Scientists IMECS 2009
[1543]
G.B. Mertzios, I. Bezakova
Computing and counting longest paths on circular-arc graphs in polynomial time
Discrete Appl. Math, in press

Inclusions

The map shows the inclusions between the current class and a fixed set of landmark classes. Minimal/maximal is with respect to the contents of ISGCI. Only references for direct inclusions are given. Where no reference is given, check equivalent classes or use the Java application. To check relations other than inclusion (e.g. disjointness) use the Java application, as well.

Map

[+]Details

Minimal superclasses

[+]Details

Maximal subclasses

[+]Details

Problems

Problems in italics have no summary page and are only listed when ISGCI contains a result for the current class.

3-Colourability
[?]
Input: A graph G in this class.
Output: True iff each vertex of G can be assigned one colour out of 3 such that whenever two vertices are adjacent, they have different colours.
Polynomial [+]Details
Clique
[?]
Input: A graph G in this class and an integer k.
Output: True iff G contains a set S of pairwise adjacent vertices, with |S| >= k.
Polynomial [+]Details
Clique cover
[?]
Input: A graph G in this class and an integer k.
Output: True iff the vertices of G can be partitioned into k sets Si, such that whenever two vertices are in the same set Si, they are adjacent.
Linear [+]Details
Cliquewidth
[?]
Whether the cliquewidth of the graphs in this class is bounded by a constant k .
The cliquewidth of a graph is the number of different labels that is needed to construct the graph using the following operations:
  • creation of a vertex with label i,
  • disjoint union,
  • renaming labels i to label j,
  • connecting all vertices with label i to all vertices with label j.
Unbounded [+]Details
Cliquewidth expression
[?]
Input: A graph G in this class.
Output: An expression that constructs G according to the rules for cliquewidth, using only a constant number of labels.
Undefined if this class has unbounded cliquewidth.
Unbounded or NP-complete [+]Details
Colourability
[?]
Input: A graph G in this class and an integer k.
Output: True iff each vertex of G can be assigned one colour out of k such that whenever two vertices are adjacent, they have different colours.
NP-complete [+]Details
Cutwidth
[?]
Input: A graph G in this class and an integer k.
Output: True iff the cutwidth of G is at most k (see bounded cutwidth).
Unknown to ISGCI [+]Details
Domination
[?]
Input: A graph G in this class and an integer k.
Output: True iff G contains a set S of vertices, with |S| <= k, such that every vertex in G is either in S or adjacent to a vertex in S.
Linear [+]Details
Feedback vertex set
[?]
Input: A graph G in this class and an integer k.
Output: True iff G contains a set S of vertices, with |S| <= k, such that every cycle in G contains a vertex from S.
Polynomial [+]Details
Graph isomorphism
[?]
Input: Graphs G and H in this class
Output: True iff G and H are isomorphic.
Unknown to ISGCI [+]Details
Hamiltonian cycle
[?]
Input: A graph G in this class.
Output: True iff G has a simple cycle that goes through every vertex of the graph.
Polynomial [+]Details
Hamiltonian path
[?]
Input: A graph G in this class.
Output: True iff G has a simple path that goes through every vertex of the graph.
Polynomial [+]Details
Independent set
[?]
Input: A graph G in this class and an integer k.
Output: True iff G contains a set S of pairwise non-adjacent vertices, such that |S| >= k.
Linear [+]Details
Maximum cut
[?]
(decision variant)
Input: A graph G in this class and an integer k.
Output: True iff the vertices of G can be partitioned into two sets A,B such that there are at least k edges in G with one endpoint in A and the other endpoint in B.
Unknown to ISGCI [+]Details
Recognition
[?]
Input: A graph G.
Output: True iff G is in this graph class.
Linear [+]Details
Treewidth
[?]
Input: A graph G in this class and an integer k.
Output: True iff the treewidth of G is at most k (see bounded treewidth).
Polynomial [+]Details
Weighted clique
[?]
Input: A graph G in this class with weight function on the vertices and a real k.
Output: True iff G contains a set S of pairwise adjacent vertices, such that the sum of the weights of the vertices in S is at least k.
Polynomial [+]Details
Weighted feedback vertex set
[?]
Input: A graph G in this class with weight function on the vertices and a real k.
Output: True iff G contains a set S of vertices, such that the sum of the weights of the vertices in S is at most k and every cycle in G contains a vertex from S.
Polynomial [+]Details
Weighted independent set
[?]
Input: A graph G in this class with weight function on the vertices and a real k.
Output: True iff G contains a set S of pairwise non-adjacent vertices, such that the sum of the weights of the vertices in S is at least k.
Polynomial [+]Details
Weighted maximum cut
[?]
(decision variant)
Input: A graph G in this class with weight function on the edges and a real k.
Output: True iff the vertices of G can be partitioned into two sets A,B such that the sum of weights of the edges in G with one endpoint in A and the other endpoint in B is at least k.
NP-complete [+]Details