Normal Helly circular-arc graphs and its subclasses
From MaRDI portal
Publication:1949109
DOI10.1016/j.dam.2012.11.005zbMath1263.05064OpenAlexW1580422088MaRDI QIDQ1949109
Min Chih Lin, Francisco J. Soulignac, Jayme Luiz Szwarcfiter
Publication date: 25 April 2013
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2012.11.005
Helly circular-arc graphsnormal circular-arc graphsproper circular-arc graphsunit circular-arc graphs
Structural characterization of families of graphs (05C75) Graph representations (geometric and intersection representations, etc.) (05C62)
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 ⋮ On neighborhood-Helly graphs ⋮ Essential obstacles to Helly circular-arc graphs ⋮ Extending partial representations of circular-arc graphs ⋮ On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid ⋮ Characterization of 2-path signed network ⋮ Parameterized complexity of induced graph matching on claw-free graphs ⋮ A certifying and dynamic algorithm for the recognition of proper circular-arc graphs ⋮ On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid ⋮ Unit interval editing is fixed-parameter tractable ⋮ Completing colored graphs to meet a target property ⋮ Dual parameterization of weighted coloring ⋮ Fully dynamic recognition of proper circular-arc graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Consecutive retrieval property -- revisited
- Linear-time recognition of Helly circular-arc models and graphs
- A simpler linear-time recognition of circular-arc graphs
- Boxicity of circular arc graphs
- Simple linear time recognition of unit interval graphs
- Clique graphs of time graphs
- Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
- The clique operator on circular-arc graphs
- Characterizations and recognition of circular-arc graphs and subclasses: a survey
- Interval graphs and interval orders
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Recognizing interval digraphs and interval bigraphs in polynomial time
- PC trees and circular-ones arrangements.
- Linear-time recognition of circular-arc graphs
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- Restricted circular-arc graphs and clique cycles
- Algorithmic graph theory and perfect graphs
- On the structure of local tournaments
- Incidence matrices and interval graphs
- The Roberts characterization of proper and unit interval graphs
- Structure theorems for some circular-arc graphs
- A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
- Short Models for Unit Interval Graphs
- Representation of a finite graph by a set of intervals on the real line
- Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
- On cliques of Helly Circular-arc Graphs
- Proper Helly Circular-Arc Graphs
- A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
- Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
- Unit Circular-Arc Graph Representations and Feasible Circulations
- An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
- A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
- Algorithms on circular-arc graphs
- Coloring a Family of Circular Arcs
- Interval bigraphs and circular arc graphs
- Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- From a Circular-Arc Model to a Proper Circular-Arc Model
- A Characterization of Comparability Graphs and of Interval Graphs
- Fully Dynamic Representations of Interval Graphs
This page was built for publication: Normal Helly circular-arc graphs and its subclasses
