Recognition of Circle Graphs

DOI10.1006/jagm.1994.1012zbMath0797.68130OpenAlexW2006383151WikidataQ56503312 ScholiaQ56503312MaRDI QIDQ4285912

Jeremy P. Spinrad

Publication date: 22 March 1994

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jagm.1994.1012

zbMATH Keywords

recognition algorithmcircle graphs

Mathematics Subject Classification ID

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

Related Items (44)

Maximum weight independent sets and cliques in intersection graphs of filaments ⋮ Notes on a theorem of Naji ⋮ Simultaneous dominance representation of multiple posets ⋮ A proof of a circle graph characterization ⋮ On polygon numbers of circle graphs and distance hereditary graphs ⋮ The complexity of colouring circle graphs ⋮ Filtering graphs to check isomorphism and extracting mapping by using the conductance electrical model ⋮ From matrix pivots to graphs in surfaces: exploring combinatorics through partial duals ⋮ Describing realizable Gauss diagrams using the concepts of parity or bipartite graphs ⋮ Circle graph isomorphism in almost linear time ⋮ Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete ⋮ Unnamed Item ⋮ Computing NodeTrix Representations of Clustered Graphs ⋮ Counting hexagonal patches and independent sets in circle graphs ⋮ Collective additive tree spanners for circle graphs and polygonal graphs ⋮ Partial characterizations of circle graphs ⋮ Parameterized domination in circle 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 ⋮ Dynamic Distance Hereditary Graphs Using Split Decomposition ⋮ Intersection representations of matrices by subtrees and unicycles on graphs ⋮ Circle graphs and monadic second-order logic ⋮ Solving some NP-complete problems using split decomposition ⋮ Minimum weight feedback vertex sets in circle graphs ⋮ Diamond-free circle graphs are Helly circle ⋮ Interlace polynomials: enumeration, unimodality and connections to codes ⋮ The interlace polynomial of a graph ⋮ NP-completeness results for edge modification problems ⋮ The expansion of a chord diagram and the Tutte polynomial ⋮ Approximating the minimum clique cover and other hard problems in subtree filament graphs ⋮ Parallel Algorithms for Maximal Cliques in Circle Graphs and Unrestricted Depth Search ⋮ Splitting cubic circle graphs ⋮ Isotropic matroids. II: Circle graphs ⋮ A characterization of circle graphs in terms of multimatroid representations ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Container ship stowage problem complexity and connection to the coloring of circle graphs ⋮ Succinct navigational oracles for families of intersection graphs on a circle ⋮ Characterizations and recognition of circular-arc graphs and subclasses: a survey ⋮ APX-hardness of domination problems in circle graphs ⋮ Approximation algorithms for vertex-connectivity augmentation on the cycle ⋮ Euler circuits and DNA sequencing by hybridization ⋮ Distributed interactive proofs for the recognition of some geometric intersection graph classes

This page was built for publication: Recognition of Circle Graphs