The interval number of a planar graph: Three intervals suffice

DOI10.1016/0095-8956(83)90050-3zbMath0528.05053OpenAlexW2071261821WikidataQ106159534 ScholiaQ106159534MaRDI QIDQ786830

Douglas B. West, Edward R. Scheinerman

Publication date: 1983

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

Full work available at URL: https://doi.org/10.1016/0095-8956(83)90050-3

zbMATH Keywords

planar graphsinterval graphinterval numberinterval representation

Mathematics Subject Classification ID

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

Related Items (28)

Interval representations of planar graphs ⋮ On an extremal problem concerning the interval number of a graph ⋮ Caterpillar arboricity of planar graphs ⋮ Irredundancy in multiple interval representations ⋮ On the interval number of special graphs ⋮ The total interval number of a graph ⋮ On the unit interval number of a graph ⋮ Tree loop graphs ⋮ Three ways to cover a graph ⋮ Edge-intersection graphs of grid paths: the bend-number ⋮ Interval numbers of powers of block graphs ⋮ On the interval number of random graphs ⋮ Scheduling split intervals with non-uniform demands ⋮ The interval number of a planar graph is at most three ⋮ On grid intersection graphs ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ On the bend-number of planar and outerplanar graphs ⋮ On the planar split thickness of graphs ⋮ Subtree and substar intersection numbers ⋮ On interval representations of graphs ⋮ Representation of Planar Hypergraphs by Contacts of Triangles ⋮ On the parameterized complexity of multiple-interval graph problems ⋮ Localized and compact data-structure for comparability graphs ⋮ On star and caterpillar arboricity ⋮ Recognizing graphs with fixed interval number is NP-complete ⋮ Distance Labeling for Permutation Graphs ⋮ A note on the interval number of a graph ⋮ Fast Diameter Computation within Split Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Recognizing graphs with fixed interval number is NP-complete
• The interval number of a complete multipartite graph
• Extremal values of the interval number of a graph, II
• On double and multiple interval graphs
• Extremal Values of the Interval Number of a Graph
• Construction of TernaryH_v-groups and TernaryP-hyperoperations

This page was built for publication: The interval number of a planar graph: Three intervals suffice