Normal Helly circular-arc graphs and its subclasses
From MaRDI portal
Publication:1949109
DOI10.1016/J.DAM.2012.11.005zbMATH Open1263.05064OpenAlexW1580422088MaRDI QIDQ1949109FDOQ1949109
Authors: Min Chih Lin, Francisco J. Soulignac, Jayme L. 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
Recommendations
- Proper Helly Circular-Arc Graphs
- Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
- Linear-time recognition of Helly circular-arc models and graphs
- Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection
- Direct and Certifying Recognition of Normal Helly Circular-Arc Graphs in Linear Time
Helly circular-arc graphsproper circular-arc graphsunit circular-arc graphsnormal circular-arc graphs
Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75)
Cites Work
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Linear-time recognition of circular-arc graphs
- Algorithmic graph theory and perfect graphs
- Incidence matrices and interval graphs
- Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
- A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
- Algorithms on circular-arc graphs
- Title not available (Why is that?)
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- Title not available (Why is that?)
- Linear-time recognition of Helly circular-arc models and graphs
- Simple linear time recognition of unit interval graphs
- Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- Representation of a finite graph by a set of intervals on the real line
- A Characterization of Comparability Graphs and of Interval Graphs
- Interval graphs and interval orders
- An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
- Title not available (Why is that?)
- Consecutive retrieval property -- revisited
- Clique graphs of time graphs
- On the structure of local tournaments
- Short models for unit interval graphs
- On cliques of Helly Circular-arc Graphs
- A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
- Title not available (Why is that?)
- Characterizations and recognition of circular-arc graphs and subclasses: a survey
- Restricted circular-arc graphs and clique cycles
- Structure theorems for some circular-arc graphs
- Coloring a Family of Circular Arcs
- Interval bigraphs and circular arc graphs
- A simpler linear-time recognition of circular-arc graphs
- The clique operator on circular-arc graphs
- PC trees and circular-ones arrangements.
- Unit Circular-Arc Graph Representations and Feasible Circulations
- Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs
- A Fully dynamic algorithm for recognizing and representing proper interval graphs
- Fully dynamic representations of interval graphs
- Recognizing interval digraphs and interval bigraphs in polynomial time
- Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
- Boxicity of circular arc graphs
- The Roberts characterization of proper and unit interval graphs
- Proper Helly Circular-Arc Graphs
- Title not available (Why is that?)
- From a Circular-Arc Model to a Proper Circular-Arc Model
Cited In (21)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Characterization of 2-path signed network
- Fully dynamic recognition of proper circular-arc graphs
- Linear-time recognition of Helly circular-arc models and graphs
- Proper Helly Circular-Arc Graphs
- Completing colored graphs to meet a target property
- A certifying and dynamic algorithm for the recognition of proper circular-arc graphs
- On some subclasses of circular-arc graphs
- Dual parameterization of weighted coloring
- Essential obstacles to Helly circular-arc graphs
- 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
- 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
- Parameterized complexity of induced graph matching on claw-free graphs
- Modification problems toward proper (Helly) circular-arc graphs
- Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
- Extending partial representations of circular-arc graphs
- A polynomial kernel for proper Helly circular-arc vertex deletion
This page was built for publication: Normal Helly circular-arc graphs and its subclasses
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1949109)
