Recognizing circle graphs in polynomial time
From MaRDI portal
Publication:4710682
DOI10.1145/65950.65951zbMATH Open0825.68417OpenAlexW1984545818MaRDI QIDQ4710682FDOQ4710682
Authors:
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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cited In (50)
- Title not available (Why is that?)
- A 2-isomorphism theorem for delta-matroids
- Independence and domination in polygon graphs
- Tree-representation of set families and applications to combinatorial decompositions
- The interlace polynomial of a graph
- \(O(m\log n)\) split decomposition of strongly-connected graphs
- Unavoidable vertex-minors in large prime graphs
- Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
- Recognition of Circle Graphs
- On strict (outer-)confluent graphs
- On strict (outer-)confluent graphs
- A Simpler Linear-Time Recognition of Circular-Arc Graphs
- The complexity of domination problems in circle graphs
- On the structure of certain intersection graphs
- Parallel algorithms for maximal cliques in circle graphs and unrestricted depth search
- On the recognition of digital circles in linear time
- \(O(m \log n)\) split decomposition of strongly connected graphs
- Completely separable graphs
- Euler circuits and DNA sequencing by hybridization
- On edge transitivity of directed graphs
- Linear-time recognition of circular-arc graphs
- An efficient algorithm to generate all maximal independent sets on trapezoid graphs
- Word-representability of graphs with respect to split recomposition
- Title not available (Why is that?)
- Counting hexagonal patches and independent sets in circle graphs
- From matrix pivots to graphs in surfaces: exploring combinatorics through partial duals
- Solving some NP-complete problems using split decomposition
- Practical and efficient split decomposition via graph-labelled trees
- APX-hardness of domination problems in circle graphs
- Using split composition to extend distance-hereditary graphs in a generative way (extended abstract)
- Notes on a theorem of Naji
- Practical and efficient circle graph recognition
- Container ship stowage problem complexity and connection to the coloring of circle graphs
- A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
- Circle graphs and monadic second-order logic
- Diamond-free circle graphs are Helly circle
- Reconnaissance des graphes de cordes
- Reducing prime graphs and recognizing circle graphs
- On polygon numbers of circle graphs and distance hereditary graphs
- The complexity of colouring circle graphs (extended abstract)
- Recognizing generalized transmission graphs of line segments and circular sectors
- Vertex-minors of graphs: a survey
- Algorithmic aspects of intersection graphs and representation hypergraphs
- Polynomial time recognition of unit circular-arc graphs
- Recognizing hyperelliptic graphs in polynomial time
- Circle graph isomorphism in almost linear time
- Title not available (Why is that?)
- A linear time algorithm to recognize circular permutation graphs
- Mutant knots and intersection graphs
- Digraph Decompositions and Eulerian Systems
This page was built for publication: Recognizing circle graphs in polynomial time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4710682)
