Extending partial representations of subclasses of chordal graphs

DOI10.1016/J.TCS.2015.02.007MaRDI QIDQ2344737zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Pavel Klavík, Jan Kratochvíl, Yota Otachi, Toshiki Saitoh

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 graphintersection representationinterval graphpartial representation extensionrestricted representation

Mathematics Subject Classification ID

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

Recommendations

• Extending Partial Representations of Subclasses of Chordal Graphs
• Extending partial representations of circle graphs
• Extending partial representations of circle graphs

Cites work

• A faster algorithm to recognize undirected path graphs
• A recognition algorithm for the intersection graphs of paths in trees
• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithmic graph theory and perfect graphs
• Bin packing with fixed number of bins revisited
• Bounded representations of interval and proper interval graphs
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• Efficient graph representations
• Extending partial representations of circle graphs
• Extending partial representations of function graphs and permutation graphs
• Extending Partial Representations of Subclasses of Chordal Graphs
• scientific article; zbMATH DE number 772760 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• Incidence matrices and interval graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Minimal obstructions for partial representations of interval graphs
• NP completeness of the edge precoloring extension problem on bipartite graphs
• Optimal greedy algorithms for indifference graphs
• Simple linear time recognition of unit interval graphs
• Simultaneous PQ-ordering with applications to constrained embedding problems
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The LBFS structure and recognition of interval graphs
• The Simultaneous Representation Problem for Chordal, Comparability and Permutation Graphs
• Topics in Intersection Graph Theory

Cited in

(21)

• On the classes of interval graphs of limited nesting and count of lengths
• The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation
• Isomorphism testing for \(T\)-graphs in FPT
• Non-inclusion and other subclasses of chordal graphs
• Efficient isomorphism for \(S_d\)-graphs and \(T\)-graphs
• Extending partial representations of circle graphs
• Extending Partial Representations of Subclasses of Chordal Graphs
• Extending Partial Orthogonal Drawings
• Extending partial orthogonal drawings
• scientific article; zbMATH DE number 7559402 (Why is no real title available?)
• Extending partial representations of circle graphs
• 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
• Partial and simultaneous transitive orientations via modular decompositions
• Recognition and isomorphism of proper \(H \)-graphs for unicyclic \(H\) in \textit{FPT}-time
• Minimal obstructions for partial representations of interval graphs
• Extending partial 1-planar drawings
• Partial and constrained level planarity
• Title not available (Why is no real title available?)

This page was built for publication: Extending partial representations of subclasses of chordal graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2344737)