Circle graph isomorphism and canonization can be solved in O((n+m)α(n+m)) time using minimal split decomposition and linear-time canonization of split trees.
Extending Partial Representations of Circle Graphs
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
The partial representation extension problem is a recently introduced generalization of the recognition problem. A circle graph is an intersection graph of chords of a circle. We study the partial representation extension problem for circle graphs, where the input consists of a graph $G$ and a partial representation $\cal R'$ giving some pre-drawn chords that represent an induced subgraph of $G$. The question is whether one can extend $\cal R'$ to a representation $\cal R$ of the entire graph $G$, i.e., whether one can draw the remaining chords into a partially pre-drawn representation to obtain a representation of $G$. Our main result is an $O(n^3)$ time algorithm for partial representation extension of circle graphs, where $n$ is the number of vertices. To show this, we describe the structure of all representations of a circle graph using split decomposition. This can be of independent interest.
fields
cs.DS 1years
2019 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Circle Graph Isomorphism in Almost Linear Time
Circle graph isomorphism and canonization can be solved in O((n+m)α(n+m)) time using minimal split decomposition and linear-time canonization of split trees.