Circularly Compatible Ones, $D$-Circularity, and Proper Circular-Arc Bigraphs
From MaRDI portal
Publication:4986807
DOI10.1137/19M1266162zbMath1462.05311arXiv1906.00321OpenAlexW3155111531MaRDI QIDQ4986807
Publication date: 28 April 2021
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1906.00321
Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items (2)
2-nested matrices: towards understanding the structure of circle graphs ⋮ Structured preferences: a literature survey
Cites Work
- Solving the canonical representation and star system problems for proper circular-arc graphs in logspace
- Bipartite permutation graphs with application to the minimum buffer size problem
- New characterizations of proper interval bigraphs
- Bipartite permutation graphs
- A new characterization of proper interval graphs
- Interval hypergraphs and D-interval hypergraphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Short proofs for interval digraphs
- Graphs and digraphs represented by intervals and circular arcs
- Optimal greedy algorithms for indifference graphs
- The Roberts characterization of proper and unit interval graphs
- On the compatibility between a graph and a simple order
- A structure theorem for the consecutive 1's property
- Matrix characterizations of circular-arc graphs
- Structure theorems for some circular-arc graphs
- Generating Bracelets in Constant Amortized Time
- Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs
- A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
- Indifference Digraphs: A Generalization of Indifference Graphs and Semiorders
- Interval bigraphs and circular arc graphs
- The recognition of indifference digraphs and generalized semiorders
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- Characterization and linear‐time detection of minimal obstructions to concave‐round graphs and the circular‐ones property
- New Characterizations of Proper Interval Bigraphs and Proper Circular Arc Bigraphs
- Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
- Circular‐Arc Bigraphs and Its Subclasses
- Incidence matrices with the consecutive 1’s property
- Transitiv orientierbare Graphen
- Characterizing circular-arc graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Circularly Compatible Ones, $D$-Circularity, and Proper Circular-Arc Bigraphs