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.
Completing orientations of partially oriented graphs
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We initiate a general study of what we call orientation completion problems. For a fixed class C of oriented graphs, the orientation completion problem asks whether a given partially oriented graph P can be completed to an oriented graph in C by orienting the (non-oriented) edges in P. Orien- tation completion problems commonly generalize several existing problems including recognition of certain classes of graphs and digraphs as well as extending representations of certain geometrically representable graphs. We study orientation completion problems for various classes of oriented graphs, including k-arc- strong oriented graphs, k-strong oriented graphs, quasi-transitive oriented graphs, local tournament, acyclic local tournaments, locally transitive tournaments, locally transitive local tournaments, in- tournaments, and oriented graphs which have directed cycle factors. We show that the orientation completion problem for each of these classes is either polynomial time solvable or NP-complete. We also show that some of the NP-complete problems become polynomial time solvable when the input oriented graphs satisfy certain extra conditions. Our results imply that the representation extension problems for proper interval graphs and for proper circular arc graphs are polynomial time solvable, which generalize a previous result.
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.