Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
From MaRDI portal
Publication:2448877
DOI10.1016/J.DAM.2012.12.021zbMATH Open1288.05054OpenAlexW1974513303MaRDI QIDQ2448877FDOQ2448877
Authors: Guillermo Durán, Luciano N. Grippo, Martín D. Safe 
Publication date: 5 May 2014
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2012.12.021
Recommendations
- Characterizations and recognition of circular-arc graphs and subclasses: a survey
- On some subclasses of circular-arc graphs
- On circular-perfect graphs: a survey
- Partial characterizations of circular-arc graphs
- Partial Characterizations of Circular-Arc Graphs
- A note on the Hadwiger number of circular arc graphs
- Circular-arc bigraphs and its subclasses
- Circular‐arc digraphs: A characterization
- Restricted circular-arc graphs and clique cycles
- Circular-arc hypergraphs: rigidity via connectedness
interval graphscircular-arc graphspermutation graphsforbidden subgraph characterizationscircle graphsmatrix characterizations
Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75)
Cites Work
- Linear-time recognition of circular-arc graphs
- Algorithmic graph theory and perfect graphs
- Incidence matrices and interval graphs
- Locally semicomplete digraphs: A generalization of tournaments
- The Complexity of Coloring Circular Arcs and Chords
- Title not available (Why is that?)
- Linear-time recognition of Helly circular-arc models and graphs
- Representation of a finite graph by a set of intervals on the real line
- The structure of claw-free graphs
- Transitiv orientierbare Graphen
- Characterization problems for graphs, partially ordered sets, lattices, and families of sets
- Circle graph obstructions
- On a unique tree representation for \(P_ 4\)-extendible graphs
- A New Class of Brittle Graphs
- Title not available (Why is that?)
- Characterizing circular-arc graphs
- Permutation Graphs and Transitive Graphs
- Coloring perfect \((K_ 4\)-e)-free graphs
- Paw-free graphs
- Decomposition of Directed Graphs
- Perfect Elimination and Chordal Bipartite Graphs
- Recognition of Circle Graphs
- Algorithms for a maximum clique and a maximum independent set of a circle graph
- Title not available (Why is that?)
- Reconnaissance des graphes de cordes
- Reducing prime graphs and recognizing circle graphs
- Bipartite graphs that are not circle graphs
- A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
- Recognizing circle graphs in polynomial time
- Partial characterizations of circle graphs
- Diamond-free circle graphs are Helly circle
- Characterizations and recognition of circular-arc graphs and subclasses: a survey
- List homomorphisms and circular arc graphs
- Structure theorems for some circular-arc graphs
- Interval bigraphs and circular arc graphs
- Two remarks on circular arc graphs
- Matrix characterizations of circular-arc graphs
- Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs
- Detecting a Theta or a Prism
- Circular-arc graphs with clique cover number two
- Partial characterizations of circular-arc graphs
- Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
- Title not available (Why is that?)
- Unimodularity and circle graphs
- A characterization of circle graphs
- Proper Helly Circular-Arc Graphs
- Circle graph obstructions under pivoting
- Title not available (Why is that?)
- Tree loop graphs
- The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
- Polynomial time recognition of unit circular-arc graphs
- On chordal proper circular arc graphs
- Strong tree-cographs are Birkhoff graphs
- Efficient construction of unit circular-arc models
- An Efficient Test for Circular-Arc Graphs
- Title not available (Why is that?)
- On Graphs Without Multicliqual Edges
- An approximation result for a periodic allocation problem
- A proof of a circle graph characterization
Cited In (22)
- Partial characterizations of 1-perfectly orientable graphs
- Essential obstacles to Helly circular-arc graphs
- 2-nested matrices: towards understanding the structure of circle graphs
- The Weisfeiler-Leman dimension of chordal bipartite graphs without bipartite claw
- Literature reviews in operations research: a new taxonomy and a meta review
- Small \(4\)-regular planar graphs that are not circle representable
- Partial Characterizations of Circular-Arc Graphs
- Treewidth, Circle Graphs, and Circular Drawings
- Treewidth, circle graphs and circular drawings
- On circular-perfect graphs: a survey
- On superperfection of edge intersection graphs of paths
- Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection
- Bipartite complements of circle graphs
- On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
- On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
- Partial characterizations of circular-arc graphs
- On non-superperfection of edge intersection graphs of paths
- A linear-time algorithm for clique-coloring problem in circular-arc graphs
- Circular-arc hypergraphs: rigidity via connectedness
- A polynomial kernel for proper Helly circular-arc vertex deletion
- Leaf sector covers with applications on circle graphs
- Forbidden induced subgraph characterization of circle graphs within split graphs
This page was built for publication: Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2448877)
