Journal of Graph Theory · 2018 · 11 citations · 25 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsRepresentation TheoryGeometric GraphsGeometric RepresentationGraph AlgorithmsGraph TheoryGraphical RepresentationGraph DecompositionsGraph-based Pattern RecognitionIntersection
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 and a partial representation giving some predrawn chords that represent an induced subgraph of . The question is whether one can extend to a representation of the entire graph , that is, whether one can draw the remaining chords into a partially predrawn representation to obtain a representation of . Our main result is an time algorithm for partial representation extension of circle graphs, where 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.
25
The strong perfect graph theorem
Maria Chudnovsky, Neil Robertson, Paul Seymour et al. · Annals of Mathematics · 2006 · 1.3K citations · Full text
The Complexity of Coloring Circular Arcs and Chords
M. R. Garey, David S. Johnson, Gary L. Miller et al. · SIAM Journal on Algebraic and Discrete Methods · 1980 · 391 citations
Decomposition of Directed Graphs
William H. Cunningham · SIAM Journal on Algebraic and Discrete Methods · 1982 · 245 citations
Sang‐il Oum · Journal of Combinatorial Theory Series B · 2005 · 230 citations