A Gap in the 42-Queue Layout Algorithm for Planar Graphs
A queue layout of a graph consists of a linear order of the vertices and a partition of the edges into queues so that no two edges in a single queue are nested. The minimum number of queues needed in a queue layout of a graph is called its queue number. The planar product structure theorem states that every planar graph is a subgraph of the strong product of a graph of simple treewidth at most $3$, a clique $K_3$, and a path. Such a strong product admits a queue layout with $49$ queues (Wood, 2005), which implies that the queue number of planar graphs is at most $49$. Recently, Bekos,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.05508
curl -X POST /api/v1/records/arxiv/2608.05508/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.05508/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'