Extending partial representations of proper and unit interval graphs

DOI10.1007/978-3-319-08404-6_22zbMATH Open1360.05167DBLPjournals/algorithmica/KlavikKORSSV17arXiv1207.6960OpenAlexW1582429505WikidataQ62048072 ScholiaQ62048072MaRDI QIDQ524367FDOQ524367

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)

Abstract: The recently introduced problem of extending partial interval representations asks, for an interval graph with some intervals pre-drawn by the input, whether the partial representation can be extended to a representation of the entire graph. In this paper, we give a linear-time algorithm for extending proper interval representations and an almost quadratic-time algorithm for extending unit interval representations. We also introduce the more general problem of bounded representations of unit interval graphs, where the input constrains the positions of some intervals by lower and upper bounds. We show that this problem is NP-complete for disconnected input graphs and give a polynomial-time algorithm for the special class of instances, where the ordering of the connected components of the input graph along the real line is prescribed. This includes the case of partial representation extension. The hardness result sharply contrasts the recent polynomial-time algorithm for bounded representations of proper interval graphs [Balko et al. ISAAC'13]. So unless $extP=extNP$, proper and unit interval representations have vastly different structure. This explains why partial representation extension problems for these different types of representations require substantially different techniques.

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

Recommendations

• Extending partial representations of proper and unit interval graphs
• Extending partial representations of interval graphs
• Extending partial representations of interval graphs
• On interval representations of graphs
• Bounded representations of interval and proper interval graphs
• scientific article; zbMATH DE number 7525517
• Extending partial representations of circle graphs
• Extending partial representations of circle graphs
• Extending partial representations of subclasses of chordal graphs
• Extending Partial Representations of Subclasses of Chordal Graphs

zbMATH Keywords

linear programmingproper interval graphunit interval graphbounded representationsintersection representationpartial representation extensionrestricted representation

Mathematics Subject Classification ID

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

Cites Work

• A new polynomial-time algorithm for linear programming
• Introduction to algorithms.
• Faster integer multiplication
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Algorithmic graph theory and perfect graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Title not available (Why is that?)
• Simple linear time recognition of unit interval graphs
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• A Characterization of Comparability Graphs and of Interval Graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Simultaneous Interval Graphs
• Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems
• The Simultaneous Representation Problem for Chordal, Comparability and Permutation Graphs
• Minimal representation of a semiorder
• On unit interval graphs with integer endpoints
• Title not available (Why is that?)
• ON EXTENDING A PARTIAL STRAIGHT-LINE DRAWING
• The LBFS Structure and Recognition of Interval Graphs
• The representation polyhedron of a semiorder.
• Extending partial representations of interval graphs
• Bounded Representations of Interval and Proper Interval Graphs
• Extending partial representations of proper and unit interval graphs
• Synthetic description of a semiorder
• Extending partial representations of subclasses of chordal graphs
• Extending Partial Representations of Circle 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
• On the Classes of Interval Graphs of Limited Nesting and Count of Lengths
• Completing orientations of partially oriented graphs

Cited In (29)

• Interval graph representation with given interval and intersection lengths
• Simple algorithms for partial and simultaneous rectangular duals with given contact orientations
• Extending partial representations of trapezoid graphs
• Proper interval graph extention problems of the complements of trees
• Extending partial representations of interval graphs
• Extending partial representations of circle graphs in near-linear time
• Title not available (Why is that?)
• On the classes of interval graphs of limited nesting and count of lengths
• Lexicographic Orientation Algorithms
• Extending partial representations of subclasses of chordal graphs
• Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter I: theory
• Extending partial representations of rectangular duals with given contact orientations
• Contact Representations of Planar Graphs: Extending a Partial Representation is Hard
• Minimal Obstructions for Partial Representations of Interval Graphs
• Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter II: algorithms
• Inserting one edge into a simple drawing is hard
• Probe interval and probe unit interval graphs on superclasses of cographs
• Extending upward planar graph drawings
• Coloring mixed and directional interval graphs
• Extending partial representations of proper and unit interval graphs
• Extending Partial Orthogonal Drawings
• Extending partial representations of circular-arc graphs
• Extending Partial Representations of Subclasses of Chordal Graphs
• Title not available (Why is that?)
• Minimal obstructions for partial representations of interval graphs
• The partial visibility representation extension problem
• Completion of the Mixed Unit Interval Graphs Hierarchy
• Extending Partial Orthogonal Drawings
• Partial and simultaneous transitive orientations via modular decompositions

This page was built for publication: Extending partial representations 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 Q524367)