Extending partial representations of proper and unit interval graphs

DOI10.1007/s00453-016-0133-zzbMath1360.05167arXiv1207.6960OpenAlexW1582429505WikidataQ62048072 ScholiaQ62048072MaRDI QIDQ524367

Ignaz Rutter, Maria Saumell, Toshiki Saitoh, Yota Otachi, Pavel Klavík, Tomáš Vyskočil, Jan Kratochvíl

Publication date: 2 May 2017

Published in: Algorithmica, Algorithm Theory – SWAT 2014 (Search for Journal in Brave)

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

zbMATH Keywords

linear programmingproper interval graphunit interval graphbounded representationsintersection representationpartial representation extensionrestricted representation

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (23)

Simple algorithms for partial and simultaneous rectangular duals with given contact orientations ⋮ Extending Partial Orthogonal Drawings ⋮ Extending partial representations of interval graphs ⋮ Minimal Obstructions for Partial Representations of Interval Graphs ⋮ Contact Representations of Planar Graphs: Extending a Partial Representation is Hard ⋮ Extending partial representations of circular-arc graphs ⋮ Partial and simultaneous transitive orientations via modular decompositions ⋮ Coloring mixed and directional interval graphs ⋮ Extending partial representations of rectangular duals with given contact orientations ⋮ Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter I: theory ⋮ Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter II: algorithms ⋮ Interval graph representation with given interval and intersection lengths ⋮ Minimal obstructions for partial representations of interval graphs ⋮ On the classes of interval graphs of limited nesting and count of lengths ⋮ Extending upward planar graph drawings ⋮ Extending partial representations of proper and unit interval graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The partial visibility representation extension problem ⋮ Inserting one edge into a simple drawing is hard ⋮ Lexicographic Orientation Algorithms ⋮ Extending Partial Orthogonal Drawings ⋮ Extending partial representations of subclasses of chordal graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On unit interval graphs with integer endpoints
• Extending partial representations of proper and unit interval graphs
• Simple linear time recognition of unit interval graphs
• A new polynomial-time algorithm for linear programming
• Synthetic description of a semiorder
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Minimal representation of a semiorder
• Algorithmic graph theory and perfect graphs
• The representation polyhedron of a semiorder.
• Extending partial representations of subclasses of chordal graphs
• Extending partial representations of interval graphs
• Extending Partial Representations of Circle Graphs
• Bounded Representations of Interval and Proper Interval Graphs
• Extending Partial Representations of Function Graphs and Permutation Graphs
• Minimal Obstructions for Partial Representations of Interval Graphs
• Contact Representations of Planar Graphs: Extending a Partial Representation is Hard
• Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter II: algorithms
• The LBFS Structure and Recognition of Interval Graphs
• Simultaneous Interval Graphs
• Faster Integer Multiplication
• Algorithmic Aspects of Vertex Elimination on Graphs
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• On the Classes of Interval Graphs of Limited Nesting and Count of Lengths
• Completing orientations of partially oriented graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• ON EXTENDING A PARTIAL STRAIGHT-LINE DRAWING
• A Characterization of Comparability Graphs and of Interval Graphs
• Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems
• The Simultaneous Representation Problem for Chordal, Comparability and Permutation Graphs

This page was built for publication: Extending partial representations of proper and unit interval graphs