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

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

(18)

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

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)