← All problems

Queue-Number of Planar Graphs

Does every planar graph have O(1)O(1) 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 xyxy is nested inside edge vwvw if v<x<y<wv<x<y<w in the linear order. The queue-number of a graph GG is the minimum number of queues in a queue layout of GG. This question amounts to asking whether every planar graph has a vertex ordering with a constant number of pairwise nested edges (called a rainbow).

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu