Extending Partial Representations of Subclasses of Chordal Graphs

DOI10.1007/978-3-642-35261-4_47MaRDI QIDQ4909561zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cited in

(8)

• Non-inclusion and other subclasses of chordal graphs
• Contact representations of planar graphs: extending a partial representation is hard
• Extending partial representations of subclasses of chordal graphs
• Minimal obstructions for partial representations of interval graphs
• The simultaneous representation problem for chordal, comparability and permutation graphs
• Extending partial representations of circle graphs
• Extending partial representations of circle graphs
• The Simultaneous Representation Problem for Chordal, Comparability and Permutation 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)