← All problems
Queue-Number of Planar Graphs
Does every planar graph have queue-number? A queue layout of a graph consists of a linear order of the vertices and a partition of the edges into non-nested queues. Edge is nested inside edge if in the linear order. The queue-number of a graph is the minimum number of queues in a queue layout of . This question amounts to asking whether every planar graph has a vertex ordering with a constant number of pairwise nested edges (called a rainbow).
