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 ...
share
research
∙
01/04/2023
Large Matchings in Maximal 1-planar graphs
It is well-known that every maximal planar graph has a matching of size ...
research
∙
12/13/2022
On computing the vertex connectivity of 1-plane graphs
A graph is called 1-plane if it has an embedding in the plane where each...
research
∙
09/01/2022
Visibility Representations of Toroidal and Klein-bottle Graphs
In this paper, we study visibility representations of graphs that are em...
research
∙
06/08/2022
Reconfiguration of Non-crossing Spanning Trees
For a set P of n points in the plane in general position, a non-crossing...
research
∙
12/12/2021
Computing the vertex connectivity of a locally maximal 1-plane graph in linear time
It is known that the vertex connectivity of a planar graph can be comput...
research
∙
08/26/2021
Optimal-area visibility representations of outer-1-plane graphs
This paper studies optimal-area visibility representations of n-vertex o...
research
∙
08/17/2021
Distant Representatives for Rectangles in the Plane
The input to the distant representatives problem is a set of n objects i...
research
∙
05/14/2021
Generalized LR-drawings of trees
The LR-drawing-method is a method of drawing an ordered rooted binary tr...
research
∙
04/25/2021
Efficiently Partitioning the Edges of a 1-Planar Graph into a Planar Graph and a Forest
1-planar graphs are graphs that can be drawn in the plane such that any ...
research
∙
02/04/2021
All Subgraphs of a Wheel are 5-Coupled-Choosable
A wheel graph consists of a cycle along with a center vertex connected t...
research
∙
09/15/2020
Drawing outer-1-planar graphs revisited
In a recent article (Auer et al, Algorithmica 2016) it was claimed that ...
research
∙
04/13/2020
Reconstructing a Polyhedron between Polygons in Parallel Slices
Given two n-vertex polygons, P=(p_1, …, p_n) lying in the xy-plane at z=...
research
∙
03/31/2020
Drawing Halin-graphs with small height
In this paper, we study how to draw Halin-graphs, i.e., planar graphs th...
research
∙
03/03/2020
Building a larger class of graphs for efficient reconfiguration of vertex colouring
A k-colouring of a graph G is an assignment of at most k colours to the ...
research
∙
02/26/2020
Finding large matchings in 1-planar graphs of minimum degree 3
A matching is a set of edges without common endpoint. It was recently sh...
research
∙
02/22/2020
On Layered Fan-Planar Graph Drawings
In this paper, we study fan-planar drawings that use h layers and are pr...
research
∙
11/11/2019
Matchings in 1-planar graphs with large minimum degree
In 1979, Nishizeki and Baybars showed that every planar graph with minim...
research
∙
11/06/2019
Are highly connected 1-planar graphs Hamiltonian?
It is well-known that every planar 4-connected graph has a Hamiltonian c...
research
∙
10/16/2019
Quasiperiodic bobbin lace patterns
Bobbin lace is a fibre art form in which threads are braided together to...
research
∙
10/03/2019
A note on 1-planar graphs with minimum degree 7
It is well-known that 1-planar graphs have minimum degree at most 7, and...
research
∙
08/20/2019
Line and Plane Cover Numbers Revisited
A measure for the visual complexity of a straight-line crossing-free dra...
research
∙
08/15/2019
Homotopy height, grid-major height and graph-drawing height
It is well-known that both the pathwidth and the outer-planarity of a gr...
research
∙
06/27/2019
Packing Boundary-Anchored Rectangles and Squares
Consider a set P of n points on the boundary of an axis-aligned square Q...
research
∙
05/02/2019
Minimum Ply Covering of Points with Disks and Squares
Following the seminal work of Erlebach and van Leeuwen in SODA 2008, we ...
research
∙
02/20/2019
Finding big matchings in planar graphs quickly
It is well-known that every n-vertex planar graph with minimum degree 3 ...
research
∙
01/06/2019
Maximum Matchings and Minimum Blocking Sets in Θ_6-Graphs
Θ_6-Graphs are important geometric graphs that have many applications es...
research
∙
12/11/2018
Finding Tutte paths in linear time
It is well-known that every 2-connected planar graph has a Tutte path, i...
research
∙
10/16/2018
Segment representations with small resolution
A segment representation of a graph is an assignment of line segments in...
research
∙
09/10/2018
Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD 2018)
These are the revised accepted papers from the 26th International Sympos...
research
∙
01/25/2018
Rollercoasters and Caterpillars
A rollercoaster is a sequence of real numbers for which every maximal co...
research
∙
10/12/2017
4-connected planar graphs are in B_3-EPG
We show that every 4-connected planar graph has a B_3-EPG representation...
research
∙
09/05/2017
Improved Bounds for Drawing Trees on Fixed Points with L-shaped Edges
Let T be an n-node tree of maximum degree 4, and let P be a set of n poi...
research
∙
08/31/2017
Drawing bobbin lace graphs, or, Fundamental cycles for a subclass of periodic graphs
In this paper, we study a class of graph drawings that arise from bobbin...
research
∙
08/31/2017
EPG-representations with small grid-size
In an EPG-representation of a graph G each vertex is represented by a pa...
research
∙
08/31/2017
A Note on Plus-Contacts, Rectangular Duals, and Box-Orthogonal Drawings
A plus-contact representation of a planar graph G is called c-balanced i...
research
∙
08/31/2017
On Upward Drawings of Trees on a Given Grid
Computing a minimum-area planar straight-line drawing of a graph is know...
research
∙
08/06/2017
Grid-Obstacle Representations with Connections to Staircase Guarding
In this paper, we study grid-obstacle representations of graphs where we...
research
∙
06/07/2017