Fully dynamic recognition of proper circular-arc graphs

Connectivity (05C40) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: We present a fully dynamic algorithm for the recognition of proper circular-arc (PCA) graphs. The allowed operations on the graph involve the insertion and removal of vertices (together with its incident edges) or edges. Edge operations cost O(log n) time, where n is the number of vertices of the graph, while vertex operations cost O(log n + d) time, where d is the degree of the modified vertex. We also show incremental and decremental algorithms that work in O(1) time per inserted or removed edge. As part of our algorithm, fully dynamic connectivity and co-connectivity algorithms that work in O(log n) time per operation are obtained. Also, an O(Delta) time algorithm for determining if a PCA representation corresponds to a co-bipartite graph is provided, where Delta is the maximum among the degrees of the vertices. When the graph is co-bipartite, a co-bipartition of each of its co-components is obtained within the same amount of time.

Review text

The dynamic recognition problem for a class of graphs \(C\) is the problem of maintaining a representation of a dynamically changing graph, while the graph belongs to \(C\). Its input is a graph \(G\) together with the sequence of operations that are to be applied on \(G\). A dynamic recognition algorithm is composed by the algorithm that builds the initial representation of \(G\) and the algorithms that apply each update on the representation. If recognition problem allows both incremental and decremental updates (incrementing/decrementing the size of \(G\)) it is called fully dynamic. This paper presents a fully dynamic algorithm for the recognition of proper circular-arc (PCA) graphs. Edge operations cost \(O(\log n)\) time, where \(n\) is the number of vertices of the graph, while vertex operations cost \(O(\log n+d)\) time, where \(d\) is the degree of the modified vertex. A circular-arc model is a family of arcs of some circle. A graph is said to admit a circular-arc model when its vertices are in a one-to-one correspondence with the arcs of the model in such a way that two vertices of the graph are adjacent if and only if their corresponding arcs have nonempty intersection. Those graphs that admit a circular-arc model are called circular-arc graphs. A circular-arc model is proper when none of its arcs is properly contained in some other arc of the model. A graph is a proper circular-arc (PCA) graph when it admits a proper circular-arc model, The authors also present incremental and decremental algorithms that work in \(O(1)\) time per inserted or removed edge and in \(O(d)\) time per vertex insertion. The following algorithms are easily obtainable from the above results: (i) fully dynamic connectivity and co-connectivity algorithms that work in \(O(\log n)\) time per operation, (ii) an \(O(\delta)\) time algorithm for determining if a PCA representation corresponds to a co-bipartite graph, where \(\delta\) is the maximum among the degrees of the vertices, (iii) an algorithm to find a minimal forbidden induced subgraph of a static graph in \(O(n+m)\) time.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: Fully dynamic recognition of proper circular-arc graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2350902)