Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs

DOI10.1002/jgt.3190200312zbMath0835.05064OpenAlexW2057221145MaRDI QIDQ4857436

Jing Huang, Pavol Hell

Publication date: 8 April 1996

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.3190200312

zbMATH Keywords

algorithmsrepresentationrecognitiontournamentorientationsinterval graphsintersection graphscomparability graphscircular are graphslexicographic two-coloring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (16)

A classification of locally semicomplete digraphs ⋮ Vertex heaviest paths and cycles in quasi-transitive digraphs ⋮ Solving the canonical representation and star system problems for proper circular-arc graphs in logspace ⋮ Extending partial representations of interval graphs ⋮ Characterizing interval graphs which are probe unit interval graphs ⋮ A recognition algorithm for simple-triangle graphs ⋮ Quasi‐transitive digraphs ⋮ Comparability digraphs: an analogue of comparability graphs ⋮ Normal Helly circular-arc graphs and its subclasses ⋮ Structural results on circular-arc graphs and circle graphs: a survey and the main open problems ⋮ Two remarks on circular arc graphs ⋮ Circular-arc hypergraphs: rigidity via connectedness ⋮ The lexicographic method for the threshold cover problem ⋮ Characterizations and recognition of circular-arc graphs and subclasses: a survey ⋮ Lexicographic Orientation Algorithms ⋮ Obstructions for acyclic local tournament orientation completions

Cites Work

• Unnamed Item
• Unnamed Item
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Transitive Orientation of Graphs and Identification of Permutation Graphs

This page was built for publication: Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs