Minimal obstructions for partial representations of interval graphs

MaRDI QIDQ668026zbMATH OpenFDO

Authors Pavel Klavík, Maria Saumell

Publication date 5 March 2019

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i4p55

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

interval graphsPQ-treescertifying algorithmpartial representation extension

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Minimal obstructions for partial representations of interval graphs
• On representing an interval graph using the minimum number of interval lengths
• On interval representations of graphs
• On computing graph minor obstruction sets
• Bounded representations of interval and proper interval graphs
• Interval minors of complete bipartite graphs

Cites work

• scientific article; zbMATH DE number 3566474 (Why is no real title available?)
• A Kuratowski-type theorem for planarity of partially embedded graphs
• A characterization of uniquely representable interval graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Bounded representations of interval and proper interval graphs
• Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. I: Theory
• Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. II: Algorithms
• Completing orientations of partially oriented graphs
• Contact representations of planar graphs: extending a partial representation is hard
• Counting Interval Graphs
• Extending partial representations of circle graphs
• Extending partial representations of function graphs and permutation graphs
• Extending partial representations of subclasses of chordal graphs
• Extending partial representations of trapezoid graphs
• Incidence matrices and interval graphs
• Incidence matrices, interval graphs and seriation in archeology
• Interval graphs and interval orders
• Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs
• Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs
• Mapping the genome
• Minimal obstructions for partial representations of interval graphs
• ON EXTENDING A PARTIAL STRAIGHT-LINE DRAWING
• On the classes of interval graphs of limited nesting and count of lengths
• Realizing Interval Graphs with Size and Distance Constraints
• Representation of a finite graph by a set of intervals on the real line
• Simultaneous PQ-ordering with applications to constrained embedding problems
• Testing Planarity of Partially Embedded Graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The LBFS structure and recognition of interval graphs
• The node-deletion problem for hereditary properties is NP-complete

Cited in

(4)

• Minimal obstructions for partial representations of interval graphs
• Minimal obstructions to ( , k )-polarity in cographs
• Sparse obstructions for minor-covering parameters
• The obstructions of a minor-closed set of graphs defined by a context-free grammar

This page was built for publication: Minimal obstructions for partial representations of interval graphs

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