2-nested matrices: towards understanding the structure of circle graphs

DOI10.1007/s00373-022-02510-1zbMath1492.05055arXiv2103.03795OpenAlexW3135838229WikidataQ114229615 ScholiaQ114229615MaRDI QIDQ2152610

Martín D. Safe, Nina Pardal, Guillermo Durán

Publication date: 8 July 2022

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2103.03795

zbMATH Keywords

split graphscircle graphsconsecutive-ones property2-nested matrices

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Directed graphs (digraphs), tournaments (05C20)

Cites Work

• Unnamed Item
• Unnamed Item
• Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
• Practical and efficient circle graph recognition
• Partial characterizations of circle graphs
• Splitting cubic circle graphs
• Reconnaissance des graphes de cordes
• Interval graphs and interval orders
• Reducing prime graphs and recognizing circle graphs
• On testing consecutive-ones property in parallel
• Circle graph obstructions
• Linear-time recognition of circular-arc graphs
• Algorithmic graph theory and perfect graphs
• Normal Helly circular-arc graphs and its subclasses
• Forbidden induced subgraph characterization of circle graphs within split graphs
• A characterization of circle graphs in terms of total unimodularity
• A characterization of circle graphs in terms of multimatroid representations
• Incidence matrices and interval graphs
• Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
• A matrix characterization of interval and proper 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
• Circle graph obstructions under pivoting
• Interval digraphs: An analogue of interval graphs
• Decomposition of Directed Graphs
• The Complexity of Coloring Circular Arcs and Chords
• Algorithms on circular-arc graphs
• Circular‐arc digraphs: A characterization
• Indifference Digraphs: A Generalization of Indifference Graphs and Semiorders
• Circularly Compatible Ones, $D$-Circularity, and Proper Circular-Arc Bigraphs
• Characterization and linear‐time detection of minimal obstructions to concave‐round graphs and the circular‐ones property
• Circular‐Arc Bigraphs and Its Subclasses
• Transitiv orientierbare Graphen
• Permutation Graphs and Transitive Graphs

This page was built for publication: 2-nested matrices: towards understanding the structure of circle graphs