Extending partial representations of subclasses of chordal graphs
From MaRDI portal
Publication:2344737
DOI10.1016/j.tcs.2015.02.007zbMath1311.05133OpenAlexW1993565567WikidataQ62048078 ScholiaQ62048078MaRDI QIDQ2344737
Yota Otachi, Toshiki Saitoh, Pavel Klavík, Jan Kratochvíl
Publication date: 18 May 2015
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2015.02.007
chordal graphinterval graphintersection representationpartial representation extensionrestricted representation
Related Items
Isomorphism testing for \(T\)-graphs in FPT, Extending Partial Orthogonal Drawings, Extending partial representations of interval graphs, Extending partial representations of circular-arc graphs, Partial and simultaneous transitive orientations via modular decompositions, Efficient isomorphism for \(S_d\)-graphs and \(T\)-graphs, 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, Recognizing Proper Tree-Graphs, Extending partial representations of proper and unit interval graphs, Unnamed Item, The partial visibility representation extension problem, On \(H\)-topological intersection graphs, Inserting one edge into a simple drawing is hard, Extending Partial Orthogonal Drawings
Cites Work
- Unnamed Item
- Unnamed Item
- Extending partial representations of proper and unit interval graphs
- Simple linear time recognition of unit interval graphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- A recognition algorithm for the intersection graphs of paths in trees
- Efficient graph representations
- Algorithmic graph theory and perfect graphs
- Optimal greedy algorithms for indifference graphs
- A faster algorithm to recognize undirected path graphs
- Incidence matrices and interval graphs
- Extending partial representations of interval graphs
- The intersection graphs of subtrees in trees are exactly the chordal 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
- The LBFS Structure and Recognition of Interval Graphs
- Bin Packing with Fixed Number of Bins Revisited
- Algorithmic Aspects of Vertex Elimination on Graphs
- Complexity Results for Multiprocessor Scheduling under Resource Constraints
- Topics in Intersection Graph Theory
- NP completeness of the edge precoloring extension problem on bipartite graphs
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- Extending Partial Representations of Subclasses of Chordal Graphs
- Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems
- The Simultaneous Representation Problem for Chordal, Comparability and Permutation Graphs