Extending partial representations of interval graphs
From MaRDI portal
Publication:2408095
DOI10.1007/s00453-016-0186-zzbMath1371.05190arXiv1306.2182OpenAlexW2964283305WikidataQ62048070 ScholiaQ62048070MaRDI QIDQ2408095
Pavel Klavík, Toshiki Saitoh, Jan Kratochvíl, Yota Otachi, Tomáš Vyskočil
Publication date: 9 October 2017
Published in: Algorithmica, Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1306.2182
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items (18)
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 ⋮ 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 ⋮ 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 ⋮ Inserting one edge into a simple drawing is hard ⋮ Extending Partial Orthogonal Drawings ⋮ Extending partial representations of subclasses of chordal graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Maintaining knowledge about temporal intervals
- Extending partial representations of proper and unit interval graphs
- The partial visibility representation extension problem
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Linear-time recognition of circular-arc graphs
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
- Algorithmic graph theory and perfect graphs
- Extending partial representations of subclasses of chordal graphs
- Optimal greedy algorithms for indifference graphs
- Incidence matrices and interval graphs
- Extending partial representations of interval graphs
- On Finding Tucker Submatrices and Lekkerkerker-Boland Subgraphs
- 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 I: theory
- The LBFS Structure and Recognition of Interval Graphs
- Simultaneous Interval Graphs
- Representation of a finite graph by a set of intervals on the real line
- Reasoning about temporal relations
- An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Topics in Intersection Graph Theory
- Graph Classes: A Survey
- Complexity and algorithms for reasoning about time
- Realizing Interval Graphs with Size and Distance Constraints
- NP completeness of the edge precoloring extension problem on bipartite graphs
- On the Classes of Interval Graphs of Limited Nesting and Count of Lengths
- Completing orientations of partially oriented graphs
- $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
- Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs
- Interval Graph Representation with Given Interval and Intersection Lengths
- Testing Planarity of Partially Embedded Graphs
- Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems
- NP‐completeness of list coloring and precoloring extension on the edges of planar graphs
- Sur deux propriétés des classes d'ensembles
- The Simultaneous Representation Problem for Chordal, Comparability and Permutation Graphs
- Graph Drawing
This page was built for publication: Extending partial representations of interval graphs
