Simultaneous representation of proper and unit interval graphs

DOI10.4230/LIPICS.ESA.2019.80MaRDI QIDQ5075828zbMATH OpenFDO

Authors Ignaz Rutter, Darren Strash, Peter Stumpf, Michael Vollmer

Publication date 11 May 2022

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

zbMATH Keywords

intersection graphsrecognition algorithmsimultaneous representationsproper/unit interval graphs

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Simultaneous interval graphs
• The Simultaneous Representation Problem for Chordal, Comparability and Permutation Graphs
• The simultaneous representation problem for chordal, comparability and permutation graphs

Cites work

• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• A Fully dynamic algorithm for recognizing and representing proper interval graphs
• A linear-time algorithm for proper interval graph recognition
• A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
• Algorithmic graph theory and perfect graphs
• Efficient graph representations
• Extending partial representations of circle graphs
• Graph Sandwich Problems
• Induced subgraph isomorphism on proper interval and bipartite permutation graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• On Some $\mathcal{NP}$ -complete SEFE Problems
• On simultaneous planar graph embeddings
• Optimal greedy algorithms for indifference graphs
• Recognition of probe proper interval graphs
• Simultaneous Geometric Graph Embeddings
• Simultaneous Graph Embeddings with Fixed Edges
• Simultaneous PQ-ordering with applications to constrained embedding problems
• Simultaneous interval graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The simultaneous representation problem for chordal, comparability and permutation graphs
• Toward a theory of planarity: Hanani-Tutte and planarity variants

Cited in

(3)

• Simultaneous Representation of Proper and Unit Interval Graphs
• Simple algorithms for partial and simultaneous rectangular duals with given contact orientations
• Partial and simultaneous transitive orientations via modular decompositions

This page was built for publication: Simultaneous representation of proper and unit interval graphs

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