Circular arc graph

• 

  On the left an arc graph and on the right a model for it

• 

  The shown biclaw is an example of a simple graph that does not have a circular arc model.

A circular arc graph is a structure of graph theory in discrete mathematics .

Be a graph . Is a family of circular arcs to a fixed radius such that holds ${\displaystyle G=(V,E)}$ ${\displaystyle {\mathcal {K}}:=\{K_{x}\}_{x\in V}}$

${\displaystyle {\begin{aligned}K_{x}\cap K_{y}\neq \emptyset \Leftrightarrow (x,y)\in E,\end{aligned}}}$

so is called circular arc model for . A graph is an arc graph if and only if it has an arc model. Arc graphs were first studied by Alan Tucker from the 1970s and then by many others. ${\displaystyle {\mathcal {K}}}$ ${\displaystyle G}$

Some sub-classes

If there is a model with the property that all circular arcs have a unit length, one speaks of a unit circular arc graph . If a family can be specified in which all inclusions of circular arcs are real inclusions, one speaks of proper circular arc graphs . If a model exists in such a way that the arcs have the Helly property as sets , the graph is also called the Helly arc graph .

The interval graphs are an important special case. In contrast to these, however, circular arc graphs are generally no longer perfect or chordal , because a circular arc model always exists for odd circular graphs. The linear restriction on the number of maximum cliques that one has in interval graphs also turns into an exponential limit.

Algorithmic Complexity of Classic Problems

	Circular arc graph
recognition	Linear ( McConnel 2003 )
3 staining	Polynomial ( Garey et al. 1980 )
Clique coverage	Linear ( Hsu and Tsai 1991 )
Independent amount	Linear ( Hsu and Tsai 1991 )
Dominant crowd	Linear ( Hsu and Tsai 1991 )
Hamilton path	Polynomial ( Mertizios and Bezák 2014 )
Hamilton circle	Polynomial ( Shih et al. 1992 )
Coloring number	NP-complete ( Garey et al. 1980 )

literature

• Michael R. Garey, David S. Johnson, Gary L. Miller, Christos H. Papadimitriou: The complexity of coloring circular arcs and chords . In: SIAM Journal on Algebraic Discrete Methods . 1, No. 2, 1980, pp. 216-227. Retrieved June 21, 2015.
• Wen-Lian Hsu, Kuo-Hui Tsai: Linear time algorithms on circular-arc graphs . In: Information Processing Letters . 40, No. 3, November 8, 1991, ISSN  0020-0190 , pp. 123-129. doi : 10.1016 / 0020-0190 (91) 90165-E . Retrieved June 21, 2015.
• W. Shih, T. Chern, W. Hsu: An $ O (n ^ 2 \ log n) $ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs . In: SIAM Journal on Computing . 21, No. 6, December 1, 1992, ISSN  0097-5397 , pp. 1026-1046. doi : 10.1137 / 0221061 . Retrieved June 21, 2015.
• George B. Mertzios, Ivona Bezáková: Computing and counting longest paths on circular-arc graphs in polynomial time . In: Discrete Applied Mathematics . 164, Part 2, February 19, 2014, ISSN  0166-218X , pp. 383-399. doi : 10.1016 / j.dam.2012.08.024 . Retrieved June 21, 2015.
• Ross M. McConnell: Linear-Time Recognition of Circular-Arc Graphs . In: Algorithmica . 37, No. 2, July 14, 2003, ISSN  0178-4617 , pp. 93-147. doi : 10.1007 / s00453-003-1032-7 .