Extending partial representations of subclasses of chordal graphs

DOI10.1016/j.tcs.2015.02.007zbMath1311.05133WikidataQ62048078 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

zbMATH Keywords

chordal graph; interval graph; intersection representation; partial representation extension; restricted representation

Mathematics Subject Classification ID

05C62: Graph representations (geometric and intersection representations, etc.)

Related Items

Unnamed Item, Extending Partial Orthogonal Drawings, Extending Partial Orthogonal Drawings, Extending upward planar graph drawings, On \(H\)-topological intersection graphs, Inserting one edge into a simple drawing is hard, Extending partial representations of circular-arc graphs, Recognizing Proper Tree-Graphs, Extending partial representations of proper and unit interval graphs, Minimal obstructions for partial representations of interval graphs, The partial visibility representation extension problem, On the classes of interval graphs of limited nesting and count of lengths, Isomorphism testing for \(T\)-graphs in FPT, Extending partial representations of interval graphs, Efficient isomorphism for \(S_d\)-graphs and \(T\)-graphs

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