1 citations · 4 across the 14 of their papers we have counts for
18 papers
On the Parameterized Complexity of Capacitated Stack and Queue Layouts with Colored Edges
Thomas Depian, Giuseppe Liotta, Fabrizio Montecchiani +1
Stack and queue layouts are two extensively studied and complementary linear representations of graphs. A stack (queue) layout of a graph consists of…
Ramsey Meets Simultaneous Planarity: Vertex Integrity and Pathwidth
Thomas Depian, Simon D. Fink, Alexander Firbas +3
We study the following simultaneous embedding problem: Given k graphs on the same vertex set with the same pairwise intersection, do they admit planar drawings that coincide on the…
A Uniform Algorithm for Strict NP on Bounded-Treedepth Graphs
Thomas Depian, Robert Ganian, Jakob Greilhuber +2
A classical well-quasi-ordering result guarantees the existence of non-uniform linear-time algorithms for all problems in Strict NP on relational structures of bounded treedepth; h…
The (Parameterized) Complexity of Ordering a Graph While Avoiding a Forbidden Pattern
Thomas Depian, Simon D. Fink, Alexander Firbas +3
In this paper, we study the Pattern Avoidance problem of determining whether a given graph admits a linear vertex order which avoids a given pattern , i.e., a vertex sequenc…
On the Recognition of Outerplanar Graphs with Queue Number 1
Michael A. Bekos, Thomas Depian, Stefan Felsner +7
A linear layout of a graph is defined as a total order of the vertices and a partition of the edges to pages. In a stack (queue) layout, no two edges on the same page may cross (ne…
Point Set Embeddability with List Constraints
Thomas Depian, Joseph Dorfer, Boris Klemz +2
Deciding whether a given graph admits a planar straight-line drawing where each vertex is placed on some point from a given finite point set is known as Point Set Embeddability and…
Paged Geophylogenies: A Coloring Approach to External Labeling with Tree Constraints
Thomas Depian, Thomas C. van Dijk, Martin Nöllenburg
Geophylogenies are a common type of diagram for visualizing the evolutionary history of species in a geographic context. As a drawing problem, these diagrams are commonly modeled a…
Realizing Planar Linkages in Polygonal Domains
Thomas Depian, Carolina Haase, Martin Nöllenburg +1
A linkage consists of a graph and an edge-length function . Deciding whether can be realized as a planar straight-line embedding in $\ma…
Revisiting Graph Modification via Disk Scaling: From One Radius to Interval-Based Radii
Thomas Depian, Frank Sommer
For a fixed graph class , the goal of -Modification is to transform an input graph into a graph using at most modifications. Vertex and edge deletions are com…
Linear Layouts Revisited: Stacks, Queues, and Exact Algorithms
Thomas Depian, Simon D. Fink, Robert Ganian +1
In spite of the extensive study of stack and queue layouts, many fundamental questions remain open concerning the complexity-theoretic frontiers for computing stack and queue layou…
Visualizing Treewidth
Alvin Chiu, Thomas Depian, David Eppstein +2
A witness drawing of a graph is a visualization that clearly shows a given property of a graph. We study and implement various drawing paradigms for witness drawings to clearly sho…
The Peculiarities of Extending Queue Layouts
Thomas Depian, Simon D. Fink, Robert Ganian +1
We consider the problem of computing -page queue layouts, which are linear arrangements of vertices accompanied with an assignment of the edges to pages from one to th…
Pathways to Tractability for Geometric Thickness
Thomas Depian, Simon Dominik Fink, Alexander Firbas +2
We study the classical problem of computing geometric thickness, i.e., finding a straight-line drawing of an input graph and a partition of its edges into as few parts as possible…
The Parameterized Complexity of Extending Stack Layouts
Thomas Depian, Simon D. Fink, Robert Ganian +1
An -page stack layout (also known as an -page book embedding) of a graph is a linear order of the vertex set together with a partition of the edge set into stack…
Constrained Boundary Labeling
Thomas Depian, Martin Nöllenburg, Soeren Terziadis +1
Boundary labeling is a technique in computational geometry used to label sets of features in an illustration. It involves placing labels along an axis-parallel bounding box and con…
Minimizing Corners in Colored Rectilinear Grids
Thomas Depian, Alexander Dobler, Christoph Kern +1
Given a rectilinear grid , in which cells are either assigned a single color, out of possible colors, or remain white, can we color white grid cells of to minimize the t…
Network Navigation with Online Delays is PSPACE-complete
Thomas Depian, Christoph Kern, Sebastian Röder +2
In public transport networks disruptions may occur and lead to travel delays. It is thus interesting to determine whether a traveler can be resilient to delays that occur unexpecte…
Transitions in Dynamic Point Labeling
Thomas Depian, Guangping Li, Martin Nöllenburg +1
The labeling of point features on a map is a well-studied topic. In a static setting, the goal is to find a non-overlapping label placement for (a subset of) point features. In a d…