Circularly compatible ones, D-circularity, and proper circular-arc bigraphs

DOI10.1137/19M1266162MaRDI QIDQ4986807zbMATH OpenOpenAlexFDO

Authors 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

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75)

Abstract: In 1969, Alan Tucker characterized proper circular-arc graphs as those graphs whose augmented adjacency matrices have the circularly compatible ones property. Moreover, he also found a polynomial-time algorithm for deciding whether any given augmented adjacency matrix has the circularly compatible ones property. These results allowed him to devise the first polynomial-time recognition algorithm for proper circular-arc graphs. However, as Tucker himself remarks, he did not solve the problems of finding a structure theorem and an efficient recognition algorithm for the circularly compatible ones property in arbitrary matrices (i.e., not restricted to augmented adjacency matrices only). In this work, we solve these problems. More precisely, we give a minimal forbidden submatrix characterization for the circularly compatible ones property in arbitrary matrices and a linear-time recognition algorithm for the same property. We derive these results from analogous ones for the related $D$-circular property. Interestingly, these results lead to a minimal forbidden induced subgraph characterization and a linear-time recognition algorithm for proper circular-arc bigraphs, solving a problem first posed by Basu, Das, Ghosh, and Sen [J. Graph Theory, 73(4):361--376, 2013]. Our findings generalize some known results about $D$-interval hypergraphs and proper interval bigraphs.

Recommendations

• Characterizations and recognition of circular-arc graphs and subclasses: a survey
• Interval bigraphs and circular arc graphs
• Circular-arc bigraphs and its subclasses
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Efficient parallel recognition of some circular arc graphs. II

Cites work

• scientific article; zbMATH DE number 3815694 (Why is no real title available?)
• scientific article; zbMATH DE number 4063153 (Why is no real title available?)
• scientific article; zbMATH DE number 15355 (Why is no real title available?)
• scientific article; zbMATH DE number 403948 (Why is no real title available?)
• scientific article; zbMATH DE number 1156626 (Why is no real title available?)
• scientific article; zbMATH DE number 1156661 (Why is no real title available?)
• scientific article; zbMATH DE number 861315 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• A new characterization of proper interval graphs
• A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
• A structure theorem for the consecutive 1's property
• Bipartite permutation graphs
• Bipartite permutation graphs with application to the minimum buffer size problem
• Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
• Characterization and linear-time detection of minimal obstructions to concave-round graphs and the circular-ones property
• Characterizations for unit interval bigraphs
• Characterizing circular-arc graphs
• Circular-arc bigraphs and its subclasses
• Generating bracelets in constant amortized time
• Graphs and digraphs represented by intervals and circular arcs
• Incidence matrices with the consecutive 1’s property
• Indifference Digraphs: A Generalization of Indifference Graphs and Semiorders
• Interval bigraphs and circular arc graphs
• Interval hypergraphs and D-interval hypergraphs
• Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Matrix characterizations of circular-arc graphs
• New characterizations of proper interval bigraphs
• New characterizations of proper interval bigraphs and proper circular arc bigraphs
• On the compatibility between a graph and a simple order
• Optimal greedy algorithms for indifference graphs
• Short proofs for interval digraphs
• Solving the canonical representation and star system problems for proper circular-arc graphs in logspace
• Structure theorems for some circular-arc graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The Roberts characterization of proper and unit interval graphs
• The recognition of indifference digraphs and generalized semiorders
• Transitiv orientierbare Graphen

Cited in

(3)

• scientific article; zbMATH DE number 2170335 (Why is no real title available?)
• 2-nested matrices: towards understanding the structure of circle graphs
• Structured preferences: a literature survey

This page was built for publication: Circularly compatible ones, \(D\)-circularity, and proper circular-arc bigraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4986807)