Extending Partial Representations of Subclasses of Chordal Graphs

DOI10.1007/978-3-642-35261-4_47zbMATH Open1260.68180arXiv1207.0255OpenAlexW1575640695MaRDI QIDQ4909561FDOQ4909561

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

Publication date: 21 March 2013

Published in: Algorithms and Computation (Search for Journal in Brave)

Abstract: Chordal graphs are intersection graphs of subtrees of a tree T. We investigate the complexity of the partial representation extension problem for chordal graphs. A partial representation specifies a tree T' and some pre-drawn subtrees of T'. It asks whether it is possible to construct a representation inside a modified tree T which extends the partial representation (i.e, keeps the pre-drawn subtrees unchanged). We consider four modifications of T' and get vastly different problems. In some cases, it is interesting to consider the complexity even if just T' is given and no subtree is pre-drawn. Also, we consider three well-known subclasses of chordal graphs: Proper interval graphs, interval graphs and path graphs. We give an almost complete complexity characterization. We further study the parametrized complexity of the problems when parametrized by the number of pre-drawn subtrees, the number of components and the size of the tree T'. We describe an interesting relation with integer partition problems. The problem Partition is used for all NP-completeness reductions. The extension of interval graphs when the space in T' is limited is "equivalent" to the BinPacking problem.

Full work available at URL: https://arxiv.org/abs/1207.0255

Recommendations

• Extending partial representations of subclasses of chordal graphs
• A generalization of chordal graphs
• On basic chordal graphs and some of its subclasses
• Representation characterizations of chordal bipartite graphs
• scientific article; zbMATH DE number 3851152
• Extending partial representations of circle graphs
• Extending partial representations of circle graphs
• Extending partial representations of proper and unit interval graphs
• Extending partial representations of proper and unit interval graphs
• Extending partial representations of interval graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph representations (geometric and intersection representations, etc.) (05C62)

Cited In (8)

• Minimal obstructions for partial representations of interval graphs
• Contact representations of planar graphs: extending a partial representation is hard
• Extending partial representations of subclasses of chordal graphs
• Non-inclusion and other subclasses of chordal graphs
• The simultaneous representation problem for chordal, comparability and permutation graphs
• Extending partial representations of proper and unit interval graphs
• The Simultaneous Representation Problem for Chordal, Comparability and Permutation Graphs
• Extending partial representations of circle graphs

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 Q4909561)