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.021zbMath1288.05054OpenAlexW1974513303MaRDI QIDQ2448877
Luciano N. Grippo, Martín D. Safe, Guillermo Durán
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
interval graphspermutation graphscircular-arc graphsforbidden subgraph characterizationscircle graphsmatrix characterizations
Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75)
Related Items (14)
2-nested matrices: towards understanding the structure of circle graphs ⋮ Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection ⋮ Essential obstacles to Helly circular-arc graphs ⋮ Bipartite complements of circle graphs ⋮ Literature reviews in operations research: a new taxonomy and a meta review ⋮ Treewidth, Circle Graphs, and Circular Drawings ⋮ 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 ⋮ A linear-time algorithm for clique-coloring problem in circular-arc graphs ⋮ Small 4-regular planar graphs that are not circle representable ⋮ The Weisfeiler-Leman dimension of chordal bipartite graphs without bipartite claw ⋮ On superperfection of edge intersection graphs of paths ⋮ Forbidden induced subgraph characterization of circle graphs within split graphs ⋮ Partial Characterizations of 1‐Perfectly Orientable Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Linear-time recognition of Helly circular-arc models and graphs
- Partial characterizations of circle graphs
- Two remarks on circular arc graphs
- A characterization of circle graphs
- Tree loop graphs
- Diamond-free circle graphs are Helly circle
- Characterizations and recognition of circular-arc graphs and subclasses: a survey
- Reconnaissance des graphes de cordes
- Coloring perfect \((K_ 4\)-e)-free graphs
- Circular-arc graphs with clique cover number two
- Unimodularity and circle graphs
- Paw-free graphs
- Reducing prime graphs and recognizing circle graphs
- Strong tree-cographs are Birkhoff graphs
- On a unique tree representation for \(P_ 4\)-extendible graphs
- The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
- Characterization problems for graphs, partially ordered sets, lattices, and families of sets
- Bipartite graphs that are not circle graphs
- Circle graph obstructions
- On chordal proper circular arc graphs
- A proof of a circle graph characterization
- Linear-time recognition of circular-arc graphs
- Algorithmic graph theory and perfect graphs
- List homomorphisms and circular arc graphs
- Incidence matrices and interval graphs
- Matrix characterizations of circular-arc graphs
- Structure theorems for some circular-arc graphs
- Representation of a finite graph by a set of intervals on the real line
- Detecting a Theta or a Prism
- A New Class of Brittle Graphs
- Locally semicomplete digraphs: A generalization of tournaments
- Proper Helly Circular-Arc Graphs
- Efficient construction of unit circular-arc models
- Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
- Circle graph obstructions under pivoting
- Partial characterizations of circular-arc graphs
- An Efficient Test for Circular-Arc Graphs
- On Graphs Without Multicliqual Edges
- A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
- Decomposition of Directed Graphs
- The Complexity of Coloring Circular Arcs and Chords
- Perfect Elimination and Chordal Bipartite Graphs
- Recognition of Circle Graphs
- Recognizing circle graphs in polynomial time
- Interval bigraphs and circular arc graphs
- Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs
- Polynomial time recognition of unit circular-arc graphs
- Transitiv orientierbare Graphen
- Characterizing circular-arc graphs
- Permutation Graphs and Transitive Graphs
- Algorithms for a maximum clique and a maximum independent set of a circle graph
- Detecting induced subgraphs
- An approximation result for a periodic allocation problem
This page was built for publication: Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
