Publications (90)
Evaluation of Labeling Strategies for Rotating Maps
Andreas Gemsa, Martin Nöllenburg, Ignaz Rutter
We consider the following problem of labeling points in a dynamic map that allows rotation. We are given a set of points in the plane labeled by a set of mutually disjoint labels,…
Upward-Planar Drawings with Bounded Span
Patrizio Angelini, Sabine Cornelsen, Giordano Da Lozzo +4
We consider upward-planar layered drawings of directed graphs, i.e., crossing-free drawings in which each edge is drawn as a y-monotone curve going upward from its tail to its head…
Morphing Rectangular Duals
Steven Chaplick, Philipp Kindermann, Jonathan Klawitter +2
A rectangular dual of a plane graph is a contact representations of by interior-disjoint axis-aligned rectangles such that (i) no four rectangles share a point and (ii) the…
Experimental Comparison of PC-Trees and PQ-Trees
Simon D. Fink, Matthias Pfretzschner, Ignaz Rutter
PQ-trees and PC-trees are data structures that represent sets of linear and circular orders, respectively, subject to constraints that specific subsets of elements have to be conse…
Consistent Labeling of Rotating Maps
Andreas Gemsa, Martin Nöllenburg, Ignaz Rutter
Dynamic maps that allow continuous map rotations, e.g., on mobile devices, encounter new issues unseen in static map labeling before. We study the following dynamic map labeling pr…
Simple -Planar Graphs are Simple -Quasiplanar
Patrizio Angelini, Michael A. Bekos, Franz J. Brandenburg +8
A simple topological graph is -quasiplanar () if it contains no pairwise crossing edges, and -planar if no edge is crossed more than times. In this paper, we…
Beyond Level Planarity
Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista +3
In this paper we settle the computational complexity of two open problems related to the extension of the notion of level planarity to surfaces different from the plane. Namely, we…
Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems
Thomas Bläsius, Ignaz Rutter
In this paper, we define and study the new problem Simultaneous PQ-Ordering. Its input consists of a set of PQ-trees, which represent sets of circular orders of their leaves, toget…
Towards a characterization of stretchable aligned graphs
Marcel Radermacher, Ignaz Rutter, Peter Stumpf
We consider the problem of stretching pseudolines in a planar straight-line drawing to straight lines while preserving the straightness and the combinatorial embedding of the drawi…
Strengthening Hardness Results to 3-Connected Planar Graphs
Giordano Da Lozzo, Ignaz Rutter
In this paper we extend some classical NP-hardness results from the class of 2-connected planar graphs to subclasses of 3-connected planar graphs. The reduction are partly based on…
Testing Mutual Duality of Planar Graphs
Patrizio Angelini, Thomas Bläsius, Ignaz Rutter
We introduce and study the problem \mpd, which asks for two planar graphs and whether can be embedded such that its dual is isomorphic to . Our algorithmic m…
Online Power-Managing Strategy with Hard Real-Time Guarantees
Jian-Jia Chen, Mong-Jen Kao, D. T. Lee +2
We consider the problem of online dynamic power management that provides hard real-time guarantees. In this problem, each of the given jobs is associated with an arrival time, a de…
Simple Realizability of Abstract Topological Graphs
Giordano Da Lozzo, Walter Didimo, Fabrizio Montecchiani +3
An abstract topological graph (AT-graph) is a pair , where is a graph and is a set of pairs of edges of . A re…
A New Perspective on Clustered Planarity as a Combinatorial Embedding Problem
Thomas Bläsius, Ignaz Rutter
The clustered planarity problem (c-planarity) asks whether a hierarchically clustered graph admits a planar drawing such that the clusters can be nicely represented by regions. We…
Optimal Orthogonal Graph Drawing with Convex Bend Costs
Thomas Bläsius, Ignaz Rutter, Dorothea Wagner
Traditionally, the quality of orthogonal planar drawings is quantified by either the total number of bends, or the maximum number of bends per edge. However, this neglects that in…
An SPQR-Tree-Like Embedding Representation for Upward Planarity
Guido Brückner, Markus Himmel, Ignaz Rutter
The SPQR-tree is a data structure that compactly represents all planar embeddings of a biconnected planar graph. It plays a key role in constrained planarity testing. We develop a…
Competitive Design and Analysis for Machine-Minimizing Job Scheduling Problem
Mong-Jen Kao, Jian-Jia Chen, Ignaz Rutter +1
We explore the machine-minimizing job scheduling problem, which has a rich history in the line of research, under an online setting. We consider systems with arbitrary job arrival…
Simultaneous FPQ-Ordering and Hybrid Planarity Testing
Giuseppe Liotta, Ignaz Rutter, Alessandra Tappini
We study the interplay between embedding constrained planarity and hybrid planarity testing. We consider a constrained planarity testing problem, called 1-Fixed Constrained Planari…
On Self-Approaching and Increasing-Chord Drawings of 3-Connected Planar Graphs
Martin Nöllenburg, Roman Prutkin, Ignaz Rutter
An -path in a drawing of a graph is self-approaching if during the traversal of the corresponding curve from to any point on the curve the distance to is non-incr…
A Kuratowski-Type Theorem for Planarity of Partially Embedded Graphs
VÃt JelÃnek, Jan KratochvÃl, Ignaz Rutter
A partially embedded graph (or PEG) is a triple (G,H,\H), where G is a graph, H is a subgraph of G, and \H is a planar embedding of H. We say that a PEG (G,H,\H) is planar if the g…
Efficient Algorithms for Ortho-Radial Graph Drawing
Benjamin Niedermann, Ignaz Rutter, Matthias Wolf
Orthogonal drawings, i.e., embeddings of graphs into grids, are a classic topic in Graph Drawing. Often the goal is to find a drawing that minimizes the number of bends on the edge…
The Partition Spanning Forest Problem
Philipp Kindermann, Boris Klemz, Ignaz Rutter +2
Given a set of colored points in the plane, we ask if there exists a crossing-free straight-line drawing of a spanning forest, such that every tree in the forest contains exactly t…
Drawing Planar Graphs with a Prescribed Inner Face
Tamara Mchedlidze, Martin Nöllenburg, Ignaz Rutter
Given a plane graph (i.e., a planar graph with a fixed planar embedding) and a simple cycle in whose vertices are mapped to a convex polygon, we consider the question w…
Operating Power Grids with Few Flow Control Buses
Thomas Leibfried, Tamara Mchedlidze, Nico Meyer-Hübner +5
Future power grids will offer enhanced controllability due to the increased availability of power flow control units (FACTS). As the installation of control units in the grid is an…
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…
Partial and Simultaneous Transitive Orientations via Modular Decomposition
Miriam Münch, Ignaz Rutter, Peter Stumpf
A natural generalization of the recognition problem for a geometric graph class is the problem of extending a representation of a subgraph to a representation of the whole graph. A…
A Simple Partially Embedded Planarity Test Based on Vertex-Addition
Simon D. Fink, Ignaz Rutter, Sandhya T. P
In the Partially Embedded Planarity problem, we are given a graph together with a topological drawing of a subgraph of . The task is to decide whether the drawing can be…
Level Planarity: Transitivity vs. Even Crossings
Guido Brückner, Ignaz Rutter, Peter Stumpf
Recently, Fulek et al. have presented Hanani-Tutte results for (radial) level planarity, i.e., a graph is (radial) level planar if it admits a (radial) level drawing where any two…
Extending Partial Representations of Proper and Unit Interval Graphs
Pavel KlavÃk, Jan KratochvÃl, Yota Otachi +4
The recently introduced problem of extending partial interval representations asks, for an interval graph with some intervals pre-drawn by the input, whether the partial representa…
NodeTrix Planarity Testing with Small Clusters
Emilio Di Giacomo, Giuseppe Liotta, Maurizio Patrignani +2
We study the NodeTrix planarity testing problem for flat clustered graphs when the maximum size of each cluster is bounded by a constant . We consider both the case when the sid…
Coloring Mixed and Directional Interval Graphs
Grzegorz Gutowski, Florian Mittelstädt, Ignaz Rutter +3
A mixed graph has a set of vertices, a set of undirected egdes, and a set of directed arcs. A proper coloring of a mixed graph is a function that assigns to each vertex in…
Intersection-Link Representations of Graphs
Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista +3
We consider drawings of graphs that contain dense subgraphs. We introduce intersection-link representations for such graphs, in which each vertex is represented by a geometric…
Gap-planar Graphs
Sang Won Bae, Jean-Francois Baffier, Jinhee Chun +8
We introduce the family of -gap-planar graphs for , i.e., graphs that have a drawing in which each crossing is assigned to one of the two involved edges and each edge…
Upward Book Embeddings of Partitioned Digraphs
Giordano Da Lozzo, Fabrizio Frati, Ignaz Rutter
In 1999, Heath, Pemmaraju, and Trenk [SIAM J. Comput. 28(4), 1999] extended the classic notion of book embeddings to digraphs, introducing the concept of upward book embeddings, in…
Parameterized Complexity of Vertex Splitting to Pathwidth at most 1
Jakob Baumann, Matthias Pfretzschner, Ignaz Rutter
Motivated by the planarization of 2-layered straight-line drawings, we consider the problem of modifying a graph such that the resulting graph has pathwidth at most 1. The problem…
Fork-forests in bi-colored complete bipartite graphs
Maria Axenovich, Marcus Krug, Georg Osang +1
Motivated by the problem in [6], which studies the relative efficiency of propositional proof systems, 2-edge colorings of complete bipartite graphs are investigated. It is shown t…
Polygon-Universal Graphs
Tim Ophelders, Ignaz Rutter, Bettina Speckmann +1
We study a fundamental question from graph drawing: given a pair of a graph and a cycle in together with a simple polygon , is there a straight-line drawing…
Simultaneous Representation of Proper and Unit Interval Graphs
Ignaz Rutter, Darren Strash, Peter Stumpf +1
In a confluence of combinatorics and geometry, simultaneous representations provide a way to realize combinatorial objects that share common structure. A standard case in the study…
Evolutionary Algorithms for One-Sided Bipartite Crossing Minimisation
Jakob Baumann, Ignaz Rutter, Dirk Sudholt
Evolutionary algorithms (EAs) are universal solvers inspired by principles of natural evolution. In many applications, EAs produce astonishingly good solutions. As they are able to…
A Topology-Shape-Metrics Framework for Ortho-Radial Graph Drawing
Lukas Barth, Benjamin Niedermann, Ignaz Rutter +1
Orthogonal drawings, i.e., embeddings of graphs into grids, are a classic topic in Graph Drawing. Often the goal is to find a drawing that minimizes the number of bends on the edge…
Many-to-One Boundary Labeling with Backbones
Michael A. Bekos, Sabine Cornelsen, Martin Fink +5
In this paper we study \emph{many-to-one boundary labeling with backbone leaders}. In this new many-to-one model, a horizontal backbone reaches out of each label into the feature-e…
Weakly Leveled Planarity with Bounded Span
Michael Bekos, Giordano Da Lozzo, Fabrizio Frati +5
This paper studies planar drawings of graphs in which each vertex is represented as a point along a sequence of horizontal lines, called levels, and each edge is either a horizonta…
Extending Partial Representations of Circular-Arc Graphs
JiÅÃ Fiala, Ignaz Rutter, Peter Stumpf +1
The partial representation extension problem generalizes the recognition problem for classes of graphs defined in terms of vertex representations. We exhibit circular-arc graphs as…
Synchronized Planarity with Applications to Constrained Planarity Problems
Thomas Bläsius, Simon D. Fink, Ignaz Rutter
We introduce the problem Synchronized Planarity. Roughly speaking, its input is a loop-free multi-graph together with synchronization constraints that, e.g., match pairs of vertice…
Multi-Sided Boundary Labeling
Philipp Kindermann, Benjamin Niedermann, Ignaz Rutter +3
In the Boundary Labeling problem, we are given a set of points, referred to as sites, inside an axis-parallel rectangle , and a set of pairwise disjoint rectangular labe…
Orthogonal Graph Drawing with Inflexible Edges
Thomas Bläsius, Sebastian Lehmann, Ignaz Rutter
We consider the problem of creating plane orthogonal drawings of 4-planar graphs (planar graphs with maximum degree 4) with constraints on the number of bends per edge. More precis…
On Turn-Regular Orthogonal Representations
Michael A. Bekos, Carla Binucci, Giuseppe Di Battista +5
An interesting class of orthogonal representations consists of the so-called turn-regular ones, i.e., those that do not contain any pair of reflex corners that "point to each other…
Graph Planarity Testing with Hierarchical Embedding Constraints
Giuseppe Liotta, Ignaz Rutter, Alessandra Tappini
Hierarchical embedding constraints define a set of allowed cyclic orders for the edges incident to the vertices of a graph. These constraints are expressed in terms of FPQ-trees. F…
Complexity of Higher-Degree Orthogonal Graph Embedding in the Kandinsky Model
Thomas Bläsius, Guido Brückner, Ignaz Rutter
We show that finding orthogonal grid-embeddings of plane graphs (planar with fixed combinatorial embedding) with the minimum number of bends in the so-called Kandinsky model (which…
Level Planarity Is More Difficult Than We Thought
Simon D. Fink, Matthias Pfretzschner, Ignaz Rutter +1
We consider three simple quadratic time algorithms for the problem Level Planarity and give a level-planar instance that they either falsely report as negative or for which they ou…
Monotone Clustered Level Planarity
Simon D. Fink, Matthias Pfretzschner, Ignaz Rutter +1
We consider the combination of the two constrained planarity problems Level- and Clustered Planarity. Traditionally, level-planar drawings with convex clusters have been studied in…
Extending Partial Orthogonal Drawings
Patrizio Angelini, Ignaz Rutter, Sandhya T P
We study the planar orthogonal drawing style within the framework of partial representation extension. Let be a partial orthogonal drawing, i.e., G is a graph, $H\sub…
Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions
Martin Nöllenburg, Roman Prutkin, Ignaz Rutter
A greedily routable region (GRR) is a closed subset of , in which each destination point can be reached from each starting point by choosing the direction with maximum…
Crossing Number of 3-Plane Drawings
Miriam Goetze, Michael Hoffmann, Ignaz Rutter +1
We study 3-plane drawings, that is, drawings of graphs in which every edge has at most three crossings. We show how the recently developed Density Formula for topological drawings…
Beyond Degree Four: Near-Orthogonal Planar Drawings
Patrizio Angelini, Sabine Cornelsen, Giordano Da Lozzo +2
Orthogonal planar drawings constitute a classical and mainstream research topic in graph drawing due to their clarity and wide applicability. In an orthogonal planar drawing of a g…
Cubic Augmentation of Planar Graphs
Tanja Hartmann, Jonathan Rollin, Ignaz Rutter
In this paper we study the problem of augmenting a planar graph such that it becomes 3-regular and remains planar. We show that it is NP-hard to decide whether such an augmentation…
Geometric Crossing-Minimization -- A Scalable Randomized Approach
Marcel Radermacher, Ignaz Rutter
We consider the minimization of edge-crossings in geometric drawings of graphs , i.e., in drawings where each edge is depicted as a line segment. The respective decision…
Graphs with Plane Outside-Obstacle Representations
Alexander Koch, Marcus Krug, Ignaz Rutter
An \emph{obstacle representation} of a graph consists of a set of polygonal obstacles and a distinct point for each vertex such that two points see each other if and only if the co…
Radial Contour Labeling with Straight Leaders
Benjamin Niedermann, Martin Nöllenburg, Ignaz Rutter
The usefulness of technical drawings as well as scientific illustrations such as medical drawings of human anatomy essentially depends on the placement of labels that describe all…
Scalable Isocontour Visualization in Road Networks via Minimum-Link Paths
Moritz Baum, Thomas Bläsius, Andreas Gemsa +2
Isocontours in road networks represent the area that is reachable from a source within a given resource limit. We study the problem of computing accurate isocontours in realistic,…
Aligned Drawings of Planar Graphs
Tamara Mchedlidze, Marcel Radermacher, Ignaz Rutter
Let be a graph that is topologically embedded in the plane and let be an arrangement of pseudolines intersecting the drawing of . An aligned drawing of and…
On -Plane Insertion into Plane Drawings
Julia Katheder, Philipp Kindermann, Fabian Klute +2
We introduce the -Plane Insertion into Plane drawing (-PIP) problem: given a plane drawing of a planar graph and a set of edges, insert the edges in into the draw…
The Influence of Dimensions on the Complexity of Computing Decision Trees
Stephen G. Kobourov, Maarten Löffler, Fabrizio Montecchiani +5
A decision tree recursively splits a feature space and then assigns class labels based on the resulting partition. Decision trees have been part of the basic machi…
Optimal Shuffle Code with Permutation Instructions
Sebastian Buchwald, Manuel Mohr, Ignaz Rutter
During compilation of a program, register allocation is the task of mapping program variables to machine registers. During register allocation, the compiler may introduce shuffle c…
Maintaining Triconnected Components under Node Expansion
Simon D. Fink, Ignaz Rutter
SPQR-trees are a central component of graph drawing and are also important in many further areas of computer science. From their inception onwards, they have always had a strong re…
Windrose Planarity: Embedding Graphs with Direction-Constrained Edges
Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista +4
Given a planar graph and a partition of the neighbors of each vertex in four sets , , , and , the problem Windrose Planarity asks to decide whet…
On 3-Coloring Circle Graphs
Patricia Bachmann, Ignaz Rutter, Peter Stumpf
Given a graph with a fixed vertex order , one obtains a circle graph whose vertices are the edges of and where two such edges are adjacent if and only if their e…
Drawing Clustered Graphs on Disk Arrangements
Tamara Mchedlidze, Marcel Radermacher, Ignaz Rutter +1
Let be a planar graph and let be a partition of . We refer to the graphs induced by the vertex sets in as Clusters. Let b…
Constrained Planarity in Practice -- Engineering the Synchronized Planarity Algorithm
Simon D. Fink, Ignaz Rutter
In the constrained planarity setting, we ask whether a graph admits a planar drawing that additionally satisfies a given set of constraints. These constraints are often derived fro…
An Integer-Linear Program for Bend-Minimization in Ortho-Radial Drawings
Benjamin Niedermann, Ignaz Rutter
An ortho-radial grid is described by concentric circles and straight-line spokes emanating from the circles' center. An ortho-radial drawing is the analog of an orthogonal drawing…
Planar Embeddings with Small and Uniform Faces
Giordano Da Lozzo, VÃt JelÃnek, Jan KratochvÃl +1
Motivated by finding planar embeddings that lead to drawings with favorable aesthetics, we study the problems MINMAXFACE and UNIFORMFACES of embedding a given biconnected multi-gra…
Inserting an Edge into a Geometric Embedding
Marcel Radermacher, Ignaz Rutter
The algorithm of Gutwenger et al. to insert an edge in linear time into a planar graph with a minimal number of crossings on , is a helpful tool for designing heuristics…
Untangling Circular Drawings: Algorithms and Complexity
Sujoy Bhore, Guangping Li, Martin Nöllenburg +2
We consider the problem of untangling a given (non-planar) straight-line circular drawing of an outerplanar graph into a planar straight-line circular drawing by…
Parameterized Complexity of Simultaneous Planarity
Simon D. Fink, Matthias Pfretzschner, Ignaz Rutter
Given input graphs , where each pair , with shares the same graph , the problem Simultaneous Embedding With Fixed Edges (SEFE) asks wh…
Simultaneous Embedding of Planar Graphs
Thomas Bläsius, Stephen G. Kobourov, Ignaz Rutter
Simultaneous embedding is concerned with simultaneously representing a series of graphs sharing some or all vertices. This forms the basis for the visualization of dynamic graphs a…
Proceedings of the 29th International Symposium on Graph Drawing and Network Visualization (GD 2021)
Helen Purchase, Ignaz Rutter
This is the arXiv index for the electronic proceedings of GD 2021, which contains the peer-reviewed and revised accepted papers with an optional appendix. Proceedings (without appe…
Simultaneous Embedding: Edge Orderings, Relative Positions, Cutvertices
Thomas Bläsius, Annette Karrer, Ignaz Rutter
A simultaneous embedding (with fixed edges) of two graphs and with common graph is a pair of planar drawings of and that coincide on . I…
Pixel and Voxel Representations of Graphs
Muhammad Jawaherul Alam, Thomas Bläsius, Ignaz Rutter +2
We study contact representations for graphs, which we call pixel representations in 2D and voxel representations in 3D. Our representations are based on the unit square grid whose…
Circle graphs can be recognized in linear time
Christophe Paul, Ignaz Rutter
To date, the best circle graph recognition algorithm runs in almost linear time as it relies on a split decomposition algorithm that uses the union-find data-structure. We show tha…
The Rique-Number of Graphs
Michael A. Bekos, Stefan Felsner, Philipp Kindermann +3
We continue the study of linear layouts of graphs in relation to known data structures. At a high level, given a data structure, the goal is to find a linear order of the vertices…
On the Relationship between -Planar and -Quasi Planar Graphs
Patrizio Angelini, Michael A. Bekos, Franz J. Brandenburg +6
A graph is -planar if it can be drawn in the plane such that no edge is crossed more than times. A graph is -quasi planar if it can be drawn in…
On the Complexity of Realizing Facial Cycles
Giordano Da Lozzo, Ignaz Rutter
We study the following combinatorial problem. Given a planar graph and a set of simple cycles in , find a planar embedding of such that t…
Using ILP/SAT to determine pathwidth, visibility representations, and other grid-based graph drawings
Therese Biedl, Thomas Bläsius, Benjamin Niedermann +3
We present a simple and versatile formulation of grid-based graph representation problems as an integer linear program (ILP) and a corresponding SAT instance. In a grid-based repre…
Clustered Planarity Variants for Level Graphs
Simon D. Fink, Matthias Pfretzschner, Ignaz Rutter +1
We consider variants of the clustered planarity problem for level-planar drawings. So far, only convex clusters have been studied in this setting. We introduce two new variants tha…
An SPQR-Tree-Like Embedding Representation for Level Planarity
Guido Brückner, Ignaz Rutter
An SPQR-tree is a data structure that efficiently represents all planar embeddings of a biconnected planar graph. It is a key tool in a number of constrained planarity testing algo…
Extending Partial Representations of Rectangular Duals with Given Contact Orientations
Steven Chaplick, Philipp Kindermann, Jonathan Klawitter +2
A rectangular dual of a graph is a contact representation of by axis-aligned rectangles such that (i)~no four rectangles share a point and (ii)~the union of all rectangles…
Towards the Recognition of Oriented Interval Graphs
Lukas P. Bachmann, JiÅà Fiala, Miriam Münch +3
Oriented interval graphs, a recent generalization of interval graphs introduced by Gutowski et al. [GD 2022], are intersection graphs of intervals, each of which is oriented either…
Planarity of Streamed Graphs
Giordano Da Lozzo, Ignaz Rutter
In this paper we introduce a notion of planarity for graphs that are presented in a streaming fashion. A is a stream of edges on a verte…
Towards a Topology-Shape-Metrics Framework for Ortho-Radial Drawings
Lukas Barth, Benjamin Niedermann, Ignaz Rutter +1
Ortho-Radial drawings are a generalization of orthogonal drawings to grids that are formed by concentric circles and straight-line spokes emanating from the circles' center. Such d…
Disconnectivity and Relative Positions in Simultaneous Embeddings
Thomas Bläsius, Ignaz Rutter
The problem Simultaneous Embedding with Fixed Edges (SEFE) asks for two planar graph and sharing a common subgraph whether…