Concept

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. Formally, let be a set of arcs. Then the corresponding circular-arc graph is G = (V, E) where and A family of arcs that corresponds to G is called an arc model. demonstrated the first polynomial recognition algorithm for circular-arc graphs, which runs in time. gave the first linear time recognition algorithm, where is the number of edges. More recently, Kaplan and Nussbaum developed a simpler linear time recognition algorithm. 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 C5, C7, etc., are circular-arc graphs. In the following, let be an arbitrary graph. 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 . is a proper circular-arc graph (also known as a circular interval graph) 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 time. They form one of the fundamental subclasses of the claw-free graphs. is a Helly circular-arc graph if there exists a corresponding arc model such that the arcs constitute a Helly family. gives a characterization of this class that implies an recognition algorithm. 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.

À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.