research
∙
09/05/2023
On 3-Coloring Circle Graphs
Given a graph G with a fixed vertex order ≺, one obtains a circle graph ...
share
research
∙
08/22/2023
Parameterized Complexity of Simultaneous Planarity
Given k input graphs G_1, … ,G_k, where each pair G_i, G_j with i ≠ j sh...
research
∙
02/28/2023
Parameterized Complexity of Vertex Splitting to Pathwidth at most 1
Motivated by the planarization of 2-layered straight-line drawings, we c...
research
∙
01/10/2023
Maintaining Triconnected Components under Node Expansion
SPQR-trees are a central component of graph drawing and are also importa...
research
∙
09/27/2022
Partial and Simultaneous Transitive Orientations via Modular Decomposition
A natural generalization of the recognition problem for a geometric grap...
research
∙
09/01/2022
The Rique-Number of Graphs
We continue the study of linear layouts of graphs in relation to known d...
research
∙
08/30/2022
Coloring Mixed and Directional Interval Graphs
A mixed graph has a set of vertices, a set of undirected egdes, and a se...
research
∙
05/16/2022
The Influence of Dimensions on the Complexity of Computing Decision Trees
A decision tree recursively splits a feature space ℝ^d and then assigns ...
research
∙
12/06/2021
Morphing Rectangular Duals
We consider the problem of morphing between rectangular duals of a plane...
research
∙
11/18/2021
Untangling Circular Drawings: Algorithms and Complexity
We consider the problem of untangling a given (non-planar) straight-line...
research
∙
09/10/2021
Proceedings of the 29th International Symposium on Graph Drawing and Network Visualization (GD 2021)
This is the arXiv index for the electronic proceedings of GD 2021, which...
research
∙
08/30/2021
Extending Partial Representations of Circular-Arc Graphs
The partial representation extension problem generalizes the recognition...
research
∙
06/28/2021
Experimental Comparison of PC-Trees and PQ-Trees
PQ-trees and PC-trees are data structures that represent sets of linear ...
research
∙
06/10/2021
A Topology-Shape-Metrics Framework for Ortho-Radial Graph Drawing
Orthogonal drawings, i.e., embeddings of graphs into grids, are a classi...
research
∙
03/11/2021
Polygon-Universal Graphs
We study a fundamental question from graph drawing: given a pair (G,C) o...
research
∙
02/03/2021
Extending Partial Representations of Rectangular Duals with Given Contact Orientations
A rectangular dual of a graph G is a contact representation of G by axis...
research
∙
09/25/2020
An SPQR-Tree-Like Embedding Representation for Level Planarity
An SPQR-tree is a data structure that efficiently represents all planar ...
research
∙
08/24/2020
An Integer-Linear Program for Bend-Minimization in Ortho-Radial Drawings
An ortho-radial grid is described by concentric circles and straight-lin...
research
∙
08/24/2020
Extending Partial Orthogonal Drawings
We study the planar orthogonal drawing style within the framework of par...
research
∙
08/20/2020
On Turn-Regular Orthogonal Representations
An interesting class of orthogonal representations consists of the so-ca...
research
∙
08/14/2020
Towards a characterization of stretchable aligned graphs
We consider the problem of stretching pseudolines in a planar straight-l...
research
∙
07/30/2020
Synchronized Planarity with Applications to Constrained Planarity Problems
We introduce the problem Synchronized Planarity. Roughly speaking, its i...
research
∙
10/22/2019
Simultaneous FPQ-Ordering and Hybrid Planarity Testing
We study the interplay between embedding constrained planarity and hybri...
research
∙
08/31/2019
Simple k-Planar Graphs are Simple (k+1)-Quasiplanar
A simple topological graph is k-quasiplanar (k≥ 2) if it contains no k p...
research
∙
08/23/2019
Simultaneous Representation of Proper and Unit Interval Graphs
In a confluence of combinatorics and geometry, simultaneous representati...
research
∙
08/01/2019
An SPQR-Tree-Like Embedding Representation for Upward Planarity
The SPQR-tree is a data structure that compactly represents all planar e...
research
∙
07/02/2019
Geometric Crossing-Minimization – A Scalable Randomized Approach
We consider the minimization of edge-crossings in geometric drawings of ...
research
∙
04/29/2019
Graph Planarity Testing with Hierarchical Embedding Constraints
Hierarchical embedding constraints define a set of allowed cyclic orders...
research
∙
03/12/2019
Efficient Algorithms for Ortho-Radial Graph Drawing
Orthogonal drawings, i.e., embeddings of graphs into grids, are a classi...
research
∙
11/02/2018
Drawing Clustered Graphs on Disk Arrangements
Let G=(V, E) be a planar graph and let C be a partition of V. We refer t...
research
∙
09/07/2018
The Partition Spanning Forest Problem
Given a set of colored points in the plane, we ask if there exists a cro...
research
∙
08/29/2018
Level Planarity: Transitivity vs. Even Crossings
Recently, Fulek et al. have presented Hanani-Tutte results for (radial) ...
research
∙
07/31/2018
Inserting an Edge into a Geometric Embedding
The algorithm of Gutwenger et al. to insert an edge e in linear time int...
research
∙
08/29/2017
Aligned Drawings of Planar Graphs
Let G be a graph topological embedded in the plane and let A be an arra...
research
∙
08/25/2017