research
∙
07/07/2023
Shallow Hitting Edge Sets in Uniform Hypergraphs
A subset M of the edges of a graph or hypergraph is hitting if M covers ...
share
research
∙
06/29/2023
Axis-Parallel Right Angle Crossing Graphs
A RAC graph is one admitting a RAC drawing, that is, a polyline drawing ...
research
∙
03/29/2023
On the complexity of embedding in graph products
Graph embedding, especially as a subgraph of a grid, is an old topic in ...
research
∙
03/23/2023
Clustered independence and bounded treewidth
A set S⊆ V of vertices of a graph G is a c-clustered set if it induces a...
research
∙
02/21/2023
Cops and Robber – When Capturing is not Surrounding
We consider "surrounding" versions of the classic Cops and Robber game. ...
research
∙
02/06/2023
Tight bound on treedepth in terms of pathwidth and longest path
We show that every graph with pathwidth strictly less than a that contai...
research
∙
01/13/2023
Primal-Dual Cops and Robber
Cops and Robber is a family of two-player games played on graphs in whic...
research
∙
11/09/2022
Directed Acyclic Outerplanar Graphs Have Constant Stack Number
The stack number of a directed acyclic graph G is the minimum k for whic...
research
∙
04/25/2022
Efficient Recognition of Subgraphs of Planar Cubic Bridgeless Graphs
It follows from the work of Tait and the Four-Color-Theorem that a plana...
research
∙
03/15/2022
On Comparable Box Dimension
Two boxes in ℝ^d are comparable if one of them is a subset of a translat...
research
∙
12/06/2021
Polychromatic Colorings of Unions of Geometric Hypergraphs
We consider the polychromatic coloring problems for unions of two or mor...
research
∙
08/23/2021
On the Queue-Number of Partial Orders
The queue-number of a poset is the queue-number of its cover graph viewe...
research
∙
08/11/2021
Linear Layouts of Complete Graphs
A page (queue) with respect to a vertex ordering of a graph is a set of ...
research
∙
07/31/2021
An improved planar graph product structure theorem
Dujmović, Joret, Micek, Morin, Ueckerdt and Wood [J. ACM 2020] proved th...
research
∙
03/31/2021
Weak Coloring Numbers of Intersection Graphs
Weak and strong coloring numbers are generalizations of the degeneracy o...
research
∙
12/15/2020
Edge-Minimum Saturated k-Planar Drawings
For a class 𝒟 of drawings of loopless multigraphs in the plane, a drawin...
research
∙
08/12/2020
The Local Queue Number of Graphs with Bounded Treewidth
A queue layout of a graph G consists of a vertex ordering of G and a par...
research
∙
07/15/2020
Plattenbauten: Touching Rectangles in Space
Planar bipartite graphs can be represented as touching graphs of horizon...
research
∙
06/24/2020
Guarding Quadrangulations and Stacked Triangulations with Edges
Let G = (V,E) be a plane graph. A face f of G is guarded by an edge vw ∈...
research
∙
04/16/2020
Four Pages Are Indeed Necessary for Planar Graphs
An embedding of a graph in a book consists of a linear order of its vert...
research
∙
01/17/2020
On Covering Numbers, Young Diagrams, and the Local Dimension of Posets
We study covering numbers and local covering numbers with respect to dif...
research
∙
08/06/2019
Engineering Negative Cycle Canceling for Wind Farm Cabling
In a wind farm turbines convert wind energy into electrical energy. The ...
research
∙
07/23/2019
Local and Union Page Numbers
We introduce the novel concepts of local and union book embeddings, and,...
research
∙
04/09/2019
Planar Graphs have Bounded Queue-Number
We show that planar graphs have bounded queue-number, thus proving a con...
research
∙
02/21/2019
A Note on Covering Young Diagrams with Applications to Local Dimension of Posets
We prove that in every cover of a Young diagram with 2kk steps with gene...
research
∙
12/03/2018
Planar Ramsey graphs
We say that a graph H is planar unavoidable if there is a planar graph G...
research
∙
11/02/2018
Planar Graphs of Bounded Degree have Constant Queue Number
A queue layout of a graph consists of a linear order of its vertices and...
research
∙
08/30/2018
The number of crossings in multigraphs with no empty lens
Let G be a multigraph with n vertices and e>4n edges, drawn in the plane...
research
∙
06/12/2018
The queue-number of posets of bounded width or height
Heath and Pemmaraju conjectured that the queue-number of a poset is boun...
research
∙
06/12/2018
The queue-number of planar posets
Heath and Pemmaraju conjectured that the queue-number of a poset is boun...
research
∙
05/08/2018
The interval number of a planar graph is at most three
The interval number of a graph G is the minimum k such that one can assi...
research
∙
03/06/2018
Induced and Weak Induced Arboricities
We define the induced arboricity of a graph G, denoted by ia(G), as the...
research
∙
12/28/2017
Beyond-Planarity: Density Results for Bipartite Graphs
Beyond-planarity focuses on the study of geometric and topological graph...
research
∙
10/06/2017