Partial and simultaneous transitive orientations via modular decompositions

DOI10.1007/s00453-023-01188-yarXiv2209.13175OpenAlexW4389742524MaRDI QIDQ6130330

Ignaz Rutter, Peter Stumpf, Miriam Münch

Publication date: 2 April 2024

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

comparability graphmodular decompositionpermutation graphsimultaneous representationcircular permutation graphrepresentation extension

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Extending partial representations of proper and unit interval graphs
• On simultaneous planar graph embeddings
• A linear-time algorithm for a special case of disjoint set union
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Modular decomposition and transitive orientation
• Extending partial representations of trapezoid graphs
• Algorithmic graph theory and perfect graphs
• A Kuratowski-type theorem for planarity of partially embedded graphs
• Extending partial representations of subclasses of chordal graphs
• Extending partial representations of interval graphs
• Extending partial representations of rectangular duals with given contact orientations
• Extending Partial Representations of Function Graphs and Permutation Graphs
• Contact Representations of Planar Graphs: Extending a Partial Representation is Hard
• Simultaneous Interval Graphs
• Fast Algorithms for Finding Nearest Common Ancestors
• Simultaneous Graph Embeddings with Fixed Edges
• Total Ordering Problem
• Circular permutation graphs
• A linear time algorithm to recognize circular permutation graphs
• Toward a Theory of Planarity: Hanani-Tutte and Planarity Variants
• Testing Simultaneous Planarity when the Common Graph is 2-Connected
• Testing Planarity of Partially Embedded Graphs
• Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems
• Extending partial representations of circle graphs
• Simultaneous Geometric Graph Embeddings
• ON EXTENDING A PARTIAL STRAIGHT-LINE DRAWING
• Transitiv orientierbare Graphen
• A Characterization of Comparability Graphs and of Interval Graphs
• On Some $\mathcal{NP}$ -complete SEFE Problems
• The Simultaneous Representation Problem for Chordal, Comparability and Permutation Graphs

This page was built for publication: Partial and simultaneous transitive orientations via modular decompositions