Delphi.science

Tripod Reordering: A 33-Queue Layout of Planar Graphs

Source: arxiv.org/abs/2611.14817

Sergey Pupyrev

arXivarxiv/2611.14817Nov 10, 2026cs.DMscore 0

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. A planar product structure theorem of Dujmović, Joret, Micek, Morin, Ueckerdt, and Wood (JACM, 2020) 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. The result has been used to show that the queue number of planar graphs is at most $49$. Recently,…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.14817
curl -X POST /api/v1/records/arxiv/2611.14817/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.14817/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'