Extending partial representations of subclasses of chordal graphs

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

zbMATH Keywords

chordal graphinterval graphintersection representationpartial representation extensionrestricted representation

Mathematics Subject Classification ID

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

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