Overview

In a total order of the vertices of a graph, two edges with no endpoint in common can be crossing, nested, or disjoint. A k-stack (respectively, k-queue) layout of a graph consists of a total order of the vertices, and a partition of the edges into k sets of pairwise non-crossing (respectively, non-nested) edges. The minimum number of pages in a stack layout (also known as book embedding) is called its stack number; it is also called book thickness, pagenumber, or fixed outerthickness. Similarly, the queue number of a graph is the smallest number of queues that are required by any queue layout of the graph. This system is developed to construct stack and queue layouts of small and medium-sized graphs. It is based on a SAT formulation of the problem and is capable to compute optimal layouts of graphs with hundreds of vertices within several minutes.

People behind the system

Sergey Pupyrev is a (former) post-doc at the University of Arizona. For questions and comments email at spupyrev+bob@gmail The source code for the system is available at Github This page surveys existing results regarding upper and lower bounds on stack, queue, and track numbers of various classes of graphs.

Changelog