An interactive verification for
Lemma 3. qn(H6) <= 3.
Lemma 3. qn(H6) <= 3.
Lemma 3. qn(H6) <= 3. (i.e., H6 = Q6 - {111111})
Proof. To show that there exists a 3-queue layout of H6, by Corollary 2, we need to partition H6 into three edge-disjoint spanning subgraphs such that each subgraph has a leveled-planar embedding with the same induced order. Figures (a), (b) and (c) shows the desired embeddings. Since every vertex of H6 has degree 6 except vertices 011111, 101111, 110111, 111011, 111101, 111110, the adjacency of vertices can be checked by a tedious process of verification from the drawing. Thus the correctness directly follows.
