Circularly Compatible Ones, $D$-Circularity, and Proper Circular-Arc Bigraphs

DOI10.1137/19M1266162zbMath1462.05311arXiv1906.00321OpenAlexW3155111531MaRDI QIDQ4986807

Martín D. Safe

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

zbMATH Keywords

circular-ones propertycircularly compatible onesproper circular-arc bigraphs

Mathematics Subject Classification ID

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