5 papers
A Gap in the 42-Queue Layout Algorithm for Planar Graphs
Sergey Pupyrev
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…
How to Draw a Planar Graph: An Experimental Evaluation
Sergey Pupyrev
Planar graphs are central to graph drawing, with extensive results on planar layouts and related structures. Every planar graph admits a planar straight-line drawing, and algorithm…
The Price of Upwardness
Patrizio Angelini, Therese Biedl, Markus Chimani +8
Not every directed acyclic graph (DAG) whose underlying undirected graph is planar admits an upward planar drawing. We are interested in pushing the notion of upward drawings beyon…
Transforming Stacks into Queues: Mixed and Separated Layouts of Graphs
Julia Katheder, Michael Kaufmann, Sergey Pupyrev +1
Some of the most important open problems for linear layouts of graphs ask for the relation between a graph's queue number and its stack number or mixed number. In such, we seek a v…
Forbidden Patterns in Mixed Linear Layouts
Deborah Haun, Laura Merker, Sergey Pupyrev
An ordered graph is a graph with a total order over its vertices. A linear layout of an ordered graph is a partition of the edges into sets of either non-crossing edges, called sta…