circular-arc graph

intersection graph for a set of arcs on a circle

Uses your system voice; voice and rate in settings.

Q5121634Snapshot

≈ 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.

Provenance

snapshot circular-arc-graph-583725-0866a8f403d4075a · hash 0866a8f403d4075a5ae7f22583a54b833f38244acb16baa9dee1a57cb4b4ebb9 · captured 1766831120.0 · version history

Cite this page as: encyclopegia.org, “circular-arc graph”, snapshot circular-arc-graph-583725-0866a8f403d4075a. https://encyclopegia.org/a/circular-arc-graph

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.