Extending partial representations of function graphs and permutation graphs

DOI10.1007/978-3-642-33090-2_58MaRDI QIDQ2912884zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Pavel Klavík, Jan Kratochvíl, Tomasz Krawczyk, Bartosz Walczak

Publication date 25 September 2012

Published in Algorithms – ESA 2012 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75)

Abstract: Function graphs are graphs representable by intersections of continuous real-valued functions on the interval [0,1] and are known to be exactly the complements of comparability graphs. As such they are recognizable in polynomial time. Function graphs generalize permutation graphs, which arise when all functions considered are linear. We focus on the problem of extending partial representations, which generalizes the recognition problem. We observe that for permutation graphs an easy extension of Golumbic's comparability graph recognition algorithm can be exploited. This approach fails for function graphs. Nevertheless, we present a polynomial-time algorithm for extending a partial representation of a graph by functions defined on the entire interval [0,1] provided for some of the vertices. On the other hand, we show that if a partial representation consists of functions defined on subintervals of [0,1], then the problem of extending this representation to functions on the entire interval [0,1] becomes NP-complete.

Recommendations

• Extending partial representations of circle graphs

Cited in

(17)

• Partial and simultaneous transitive orientations via modular decompositions
• Minimal obstructions for partial representations of interval graphs
• Partial and constrained level planarity
• Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. I: Theory
• Extending partial representations of circle graphs in near-linear time
• scientific article; zbMATH DE number 7559402 (Why is no real title available?)
• scientific article; zbMATH DE number 4063148 (Why is no real title available?)
• Contact representations of planar graphs: extending a partial representation is hard
• On the classes of interval graphs of limited nesting and count of lengths
• A functional approach to the representation of graphs
• Extending partial representations of subclasses of chordal graphs
• Extending partial 1-planar drawings
• Simultaneous contact representations of planar graphs
• Functigraphs: An extension of permutation graphs
• Inserting one edge into a simple drawing is hard
• Extending partial representations of circular-arc graphs
• Minimal obstructions for partial representations of interval graphs

This page was built for publication: Extending partial representations of function graphs and permutation graphs

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