У теорії графів графом дуг кола називають граф перетинів множини дуг кола. Граф має одну вершину для кожної дуги кола і ребро між двома вершинами, якщо відповідні дуги перетинаються.
Формально, нехай
— множина дуг. Тоді відповідний їм граф дуг кола — це G = (V, E), де
і
Сімейство дуг, відповідне графу G, називають дугового моделлю.
Розпізнавання Тукер знайшов перший поліноміальний алгоритм розпізнавання для графів дуг кола, що працює за час . Пізніше Макконнел знайшов перший лінійний алгоритм розпізнавання за час .
Зв'язок з іншими класами графів Графи дуг кола є природним узагальненням інтервальних графів. Якщо граф дуг кола G має дугову модель, що не покриває деяких точок кола, коло можна розірвати в такій точці і випростати у відрізок, що дає інтервальне подання. Однак, на відміну від інтервальних графів, графи дуг кола не завжди досконалі, оскільки непарні цикли без хорд C5, C7 тощо є графами дуг кола.
Деякі підкласи Нижче нехай — довільний граф.
Графи одиничних дуг кола є графом одиничних дуг кола, якщо існує дугова модель, у якій всі дуги мають однакову довжину.
Правильні графи дуг кола є правильним графом дуг кола (або цикловим інтервальним графом), якщо існує відповідна дугова модель, у якій жодна дуга не містить повністю іншої. Розпізнати такий граф і побудувати правильну дугову модель можна за лінійний час .
Циркулярні графи дуг Геллі є циркулярним графом дуг Геллі, якщо існує відповідна дугова модель така, що дуги утворюють сімейство Геллі. Гаврил дає опис цього класу, з якого випливає алгоритм розпізнавання за час .
Йоріс і співавтори дають інші характеристики (зокрема, перелік заборонених породжених підграфів) цього класу, звідки випливає алгоритм розпізнавання, що працює за час O(n+m). Якщо вхідний граф не є циркулярним графом дуг Геллі, то алгоритм повертає підтвердження цього факту у вигляді забороненого породженого підграфа. Вони дали також алгоритм визначення, чи утворює дана циркулярна дугова модель сімейство Геллі, за час O(n).
Застосування Циркулярні графи дуг корисні в моделюванні задач періодичного розподілу ресурсів у дослідженні операцій. Кожен інтервал подає запит на певний період, повторюваний у часі.
Див. також Граф одиничних кругів
Примітки
Посилання . .
Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004. .
.