Simultaneous representation of proper and unit interval graphs

DOI10.4230/LIPICS.ESA.2019.80MaRDI QIDQ5075828FDOQ5075828

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

Recommendations

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

zbMATH Keywords

intersection graphsrecognition algorithmsimultaneous representationsproper/unit interval graphs

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

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

Cited In (3)

• Simple algorithms for partial and simultaneous rectangular duals with given contact orientations
• Extending partial representations of proper and unit interval graphs
• 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)