112 citations · 298 across the 40 of their papers we have counts for
45 papers
Smallest Cubic Non-1-Planar Graphs
Sergey Pupyrev
A graph is 1-planar if it has a drawing in which every edge is crossed at most once. We show that the smallest cubic non-1-planar graphs have vertices. Two such graphs are the…
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…
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…
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…
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…
Linear Layouts of Bipartite Planar Graphs
Henry Förster, Michael Kaufmann, Laura Merker +2
A linear layout of a graph consists of a linear order of the vertices and a partition of the edges. A part is called a queue (stack) if no two edges nest (cross), tha…
Optimizing Function Layout for Mobile Applications
Ellis Hoag, Kyungwoo Lee, Julián Mestre +1
Function layout, also referred to as function reordering or function placement, is one of the most effective profile-guided compiler optimizations. By reordering functions in a bin…
Minimum Coverage Instrumentation
Li Chen, Ellis Hoag, Kyungwoo Lee +2
Modern compilers leverage block coverage profile data to carry out downstream profile-guided optimizations to improve the runtime performance and the size of a binary. Given a cont…
Queue Layouts of Two-Dimensional Posets
Sergey Pupyrev
The queue number of a poset is the queue number of its cover graph when the vertex order is a linear extension of the poset. Heath and Pemmaraju conjectured that every poset of wid…
Robust and fair work allocation
Amine Allouah, Christian Kroer, Xuan Zhang +6
In today's digital world, interaction with online platforms is ubiquitous, and thus content moderation is important for protecting users from content that do not comply with pre-es…
Matching Algorithms for Blood Donation
Duncan C McElfresh, Christian Kroer, Sergey Pupyrev +5
Global demand for donated blood far exceeds supply, and unmet need is greatest in low- and middle-income countries; experts suggest that large-scale coordination is necessary to al…
On the Extended TSP Problem
Julián Mestre, Sergey Pupyrev, Seeun William Umboh
We initiate the theoretical study of Ext-TSP, a problem that originates in the area of profile-guided binary optimization. Given a graph with positive edge weights $w: E…
The Mixed Page Number of Graphs
Jawaherul Md. Alam, Michael A. Bekos, Martin Gronemann +2
A linear layout of a graph typically consists of a total vertex order, and a partition of the edges into sets of either non-crossing edges, called stacks, or non-nested edges, call…
On Families of Planar DAGs with Constant Stack Number
Martin Nöllenburg, Sergey Pupyrev
A -stack layout (or -page book embedding) of a graph consists of a total order of the vertices, and a partition of the edges into sets of non-crossing edges with respect…
Lazy Queue Layouts of Posets
Jawaherul Md. Alam, Michael A. Bekos, Martin Gronemann +2
We investigate the queue number of posets in terms of their width, that is, the maximum number of pairwise incomparable elements. A long-standing conjecture of Heath and Pemmaraju…
The Turing Test for Graph Drawing Algorithms
Helen C. Purchase, Daniel Archambault, Stephen Kobourov +3
Do algorithms for drawing graphs pass the Turing Test? That is, are their outputs indistinguishable from graphs drawn by humans? We address this question through a human-centred ex…
Book Embeddings of Graph Products
Sergey Pupyrev
A -stack layout (also called a -page book embedding) of a graph consists of a total order of the vertices, and a partition of the edges into sets of non-crossing edges wi…
Four Pages Are Indeed Necessary for Planar Graphs
Michael A. Bekos, Michael Kaufmann, Fabian Klute +3
An embedding of a graph in a book consists of a linear order of its vertices along the spine of the book and of an assignment of its edges to the pages of the book, so that no two…
Improved Bounds for Track Numbers of Planar Graphs
Sergey Pupyrev
A track layout of a graph consists of a vertex coloring and a total order of each color class, such that no two edges cross between any two color classes. The track number of a gra…
Multi-Dimensional Balanced Graph Partitioning via Projected Gradient Descent
Dmitrii Avdiukhin, Sergey Pupyrev, Grigory Yaroslavtsev
Motivated by performance optimization of large-scale graph processing systems that distribute the graph across multiple machines, we consider the balanced graph partitioning proble…
Bandana: Using Non-volatile Memory for Storing Deep Learning Models
Assaf Eisenman, Maxim Naumov, Darryl Gardner +5
Typical large-scale recommender systems use deep learning models that are stored on a large amount of DRAM. These models often rely on embeddings, which consume most of the require…
Queue Layouts of Planar 3-Trees
Jawaherul Md. Alam, Michael A. Bekos, Martin Gronemann +2
A queue layout of a graph G consists of a linear order of the vertices of G and a partition of the edges of G into queues, so that no two independent edges of the same queue are ne…
Improved Basic Block Reordering
Andy Newell, Sergey Pupyrev
Basic block reordering is an important step for profile-guided binary optimization. The state-of-the-art goal for basic block reordering is to maximize the number of fall-through b…