Structure theorems for some circular-arc graphs

DOI10.1016/S0012-365X(74)80027-0zbMath0269.05119OpenAlexW2063227364MaRDI QIDQ2563173

Publication date: 1974

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0012-365x(74)80027-0

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Permutations, words, matrices (05A05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph theory (05C99)

Related Items (49)

Circular-arc graphs with clique cover number two ⋮ The Complexity of Coloring Circular Arcs and Chords ⋮ From a Circular-Arc Model to a Proper Circular-Arc Model ⋮ On the problem of how to represent a graph taking into account an additional structure ⋮ Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection ⋮ Solving the canonical representation and star system problems for proper circular-arc graphs in logspace ⋮ Essential obstacles to Helly circular-arc graphs ⋮ Unit ball graphs on geodesic spaces ⋮ Algorithmic aspects of intersection graphs and representation hypergraphs ⋮ Circular‐Arc Bigraphs and Its Subclasses ⋮ Proper circular arc graphs as intersection graphs of paths on a grid ⋮ Extending partial representations of circular-arc graphs ⋮ Partial Characterizations of Circular-Arc Graphs ⋮ New characterizations of proper interval bigraphs ⋮ Proper Helly Circular-Arc Graphs ⋮ Normal Helly circular-arc graphs and its subclasses ⋮ Proper interval vertex deletion ⋮ Partial characterizations of circle graphs ⋮ Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter I: theory ⋮ Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter II: algorithms ⋮ Structural results on circular-arc graphs and circle graphs: a survey and the main open problems ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ Boxicity of circular arc graphs ⋮ A certifying and dynamic algorithm for the recognition of proper circular-arc graphs ⋮ Unit interval editing is fixed-parameter tractable ⋮ An extension of a fixed point problem for simple graphs ⋮ Unit Interval Graphs of Open and Closed Intervals ⋮ The strong perfect graph conjecture holds for diamonded odd cycle-free graphs ⋮ Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs ⋮ Efficient parallel recognition of some circular arc graphs. I ⋮ Unnamed Item ⋮ Mixed unit interval graphs ⋮ An approximation result for a periodic allocation problem ⋮ Cyclic orders ⋮ Characterization problems for graphs, partially ordered sets, lattices, and families of sets ⋮ Proper Interval Vertex Deletion ⋮ Completing colored graphs to meet a target property ⋮ A constant factor approximation algorithm for boxicity of circular arc graphs ⋮ Hadwiger's conjecture for proper circular arc graphs ⋮ Representation theorems for graphs whose vertex set is partially ordered ⋮ Circularly Compatible Ones, $D$-Circularity, and Proper Circular-Arc Bigraphs ⋮ Partial characterizations of circular-arc graphs ⋮ Characterizations and recognition of circular-arc graphs and subclasses: a survey ⋮ On a circle-cover minimization problem ⋮ An O(qn) algorithm to q-color a proper family of circular arcs ⋮ Circular representation problem on hypergraphs ⋮ Fully dynamic recognition of proper circular-arc graphs ⋮ An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs ⋮ Graphs and digraphs represented by intervals and circular arcs

Cites Work

This page was built for publication: Structure theorems for some circular-arc graphs