The interval number of a planar graph is at most three

DOI10.1016/j.jctb.2020.07.006zbMath1457.05025arXiv1805.02947OpenAlexW3048492929MaRDI QIDQ2221918

Kolja Knauer, Torsten Ueckerdt, Guillaume Guégan, Jonathan Rollin

Publication date: 3 February 2021

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

planar graphsinterval graphsinterval numbergeometric intersection graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Cites Work

• Recognizing graphs with fixed interval number is NP-complete
• The interval number of a planar graph: Three intervals suffice
• Three ways to cover a graph
• On star and caterpillar arboricity
• Interval representations of planar graphs
• Decomposing 4-connected planar triangulations into two trees and one path
• Caterpillar arboricity of planar graphs
• Recognizing \(d\)-interval graphs and \(d\)-track interval graphs
• Planar Graphs as VPG-Graphs
• Visibility Number of Directed Graphs
• On double and multiple interval graphs
• A sharp edge bound on the interval number of a graph
• On the interval number of special graphs
• Every planar graph is the intersection graph of segments in the plane
• On interval representations of graphs

This page was built for publication: The interval number of a planar graph is at most three