On interval representations of graphs

DOI10.1016/J.DAM.2015.08.022MaRDI QIDQ5962513zbMATH OpenOpenAlexFDO

Authors Aquiles Braga de Queiroz, Valentin Garnero, Pascal Ochem

Publication date 12 February 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2015.08.022

zbMATH Keywords

NP-completenessplanar graphsinterval numbertrack number

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• The interval number of a planar graph is at most three
• Recognizing graphs with fixed interval number is NP-complete
• scientific article; zbMATH DE number 1185295
• The total interval number of a graph
• scientific article; zbMATH DE number 846956

Cites work

• scientific article; zbMATH DE number 1185295 (Why is no real title available?)
• Caterpillar arboricity of planar graphs
• On star and caterpillar arboricity
• On the interval number of special graphs
• On the maximum average degree and the oriented chromatic number of a graph
• Recognizing d-interval graphs and d-track interval graphs
• Recognizing graphs with fixed interval number is NP-complete
• The Complexity of Multiterminal Cuts
• The interval number of a planar graph: Three intervals suffice
• Three ways to cover a graph

Cited in

(16)

• Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
• On graph algebras from interval maps
• Recognizing graphs with fixed interval number is NP-complete
• The interval number of a planar graph is at most three
• Track number of line graphs
• Regular set of representatives for time-constrained MSC graphs
• scientific article; zbMATH DE number 927077 (Why is no real title available?)
• scientific article; zbMATH DE number 1923007 (Why is no real title available?)
• Succinct encodings for families of interval graphs
• Realizing Interval Graphs with Size and Distance Constraints
• scientific article; zbMATH DE number 1185295 (Why is no real title available?)
• scientific article; zbMATH DE number 701114 (Why is no real title available?)
• Interval Graphs with Containment Restrictions
• Recognizing \(d\)-interval graphs and \(d\)-track interval graphs
• Minimal obstructions for partial representations of interval graphs
• Fully dynamic representations of interval graphs

This page was built for publication: On interval representations of graphs

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