The forbidden-pattern characterization conjecture for one-stack one-queue layouts
The forbidden-pattern characterization conjecture for one-stack one-queue layouts
Let an ordered matching have a fixed non-separated layout. A -stack -queue layout uses one stack and one queue, and a mixed layout on page uses one page whose edges may be assigned to stacks or queues. The twelve and eight patterns referred to below are the patterns depicted in the source's figures.
Forbidden-pattern characterization conjecture. The ordered matching admits
and admits a mixed layout on one page if and only if it avoids the 8 patterns depicted in the source's figure.
This conjecture proposes complete finite obstruction sets for the two smallest non-separated layout classes. It is consistent with the preceding computational enumeration of twelve and eight critical matchings, but the supplied source gives no proof or resolution.
Sources & referencesView supporting material
Primary source
Deborah Haun, Laura Merker and Sergey Pupyrev, “Forbidden Patterns in Mixed Linear Layouts”, arXiv:2412.12786 (2024).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.