Recognizing circle graphs in polynomial time

DOI10.1145/65950.65951zbMath0825.68417OpenAlexW1984545818MaRDI QIDQ4710682

No author found.

Publication date: 25 June 1992

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/65950.65951

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

On the structure of certain intersection graphs ⋮ On edge transitivity of directed graphs ⋮ Notes on a theorem of Naji ⋮ Reducing prime graphs and recognizing circle graphs ⋮ Algorithmic aspects of intersection graphs and representation hypergraphs ⋮ On Strict (Outer-)Confluent Graphs ⋮ A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion ⋮ On polygon numbers of circle graphs and distance hereditary graphs ⋮ The complexity of colouring circle graphs ⋮ From matrix pivots to graphs in surfaces: exploring combinatorics through partial duals ⋮ Circle graph isomorphism in almost linear time ⋮ Tree-representation of set families and applications to combinatorial decompositions ⋮ Counting hexagonal patches and independent sets in circle graphs ⋮ Digraph Decompositions and Eulerian Systems ⋮ Completely separable graphs ⋮ On strict (outer-)confluent graphs ⋮ Structural results on circular-arc graphs and circle graphs: a survey and the main open problems ⋮ Practical and efficient circle graph recognition ⋮ Practical and efficient split decomposition via graph-labelled trees ⋮ Mutant knots and intersection graphs ⋮ Circle graphs and monadic second-order logic ⋮ Using Split Composition to Extend Distance-Hereditary Graphs in a Generative Way ⋮ Solving some NP-complete problems using split decomposition ⋮ Independence and domination in polygon graphs ⋮ Diamond-free circle graphs are Helly circle ⋮ The complexity of domination problems in circle graphs ⋮ \(O(m\log n)\) split decomposition of strongly-connected graphs ⋮ The interlace polynomial of a graph ⋮ A 2-isomorphism theorem for delta-matroids ⋮ Parallel Algorithms for Maximal Cliques in Circle Graphs and Unrestricted Depth Search ⋮ Unavoidable vertex-minors in large prime graphs ⋮ Unnamed Item ⋮ Container ship stowage problem complexity and connection to the coloring of circle graphs ⋮ O(m logn) Split Decomposition of Strongly Connected Graphs ⋮ APX-hardness of domination problems in circle graphs ⋮ Euler circuits and DNA sequencing by hybridization ⋮ An efficient algorithm to generate all maximal independent sets on trapezoid graphs