circular-arc graph
intersection graph for a set of arcs on a circle
≈ 2 min read
Names in other languages
- Русскийграф дуг окружности
- Englishcircular-arc graph
- DeutschKreisbogengraph
- 中文circular-arc 图
- Українськаграф дуг кола
- Magyarívgráf
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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 : 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 : V = \{I_1, I_2, \ldots, I_n\} and : \{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.
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 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 V = \{I_1, I_2, \ldots, I_n\} and \{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. In the following, let G = (V,E) be an arbitrary graph.
References
. . . . Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004. . . .
Text derived from https://en.wikipedia.org/w/index.php?oldid=1329679143 under CC BY-SA 4.0; modifications have been made.