Michael Hoffmann

Last Name

Hoffmann

First Name

Michael

ORCID

0000-0001-5307-7106

Organisational unit

03672 - Steger, Angelika / Steger, Angelika

Show all metadata

Search Results

Publications 1 - 10 of 23

Bounding and Computing Obstacle Numbers of Graphs
Balko, Martin; Chaplick, Steven; Ganian, Robert; et al. (2024)
SIAM Journal on Discrete Mathematics
An obstacle representation of a graph G consists of a set of pairwise disjoint simply connected closed regions and a one-to-one mapping of the vertices of G to points such that two vertices are adjacent in G if and only if the line segment connecting the two corresponding points does not intersect any obstacle. The obstacle number of a graph is the smallest number of obstacles in an obstacle representation of the graph in the plane such that all obstacles are simple polygons. It is known that the obstacle number of each n-vertex graph is O(nlogn [M. Balko, J. Cibulka, and P. Valtr, Discrete Comput. Geom., 59 (2018), pp. 143–164] and that there are n-vertex graphs whose obstacle number is Ω(n/(loglogn)²) [V. Dujmović and P. Morin, Electron. J. Combin., 22 (2015), 3.1]. We improve this lower bound to Ω(n/loglogn) for simple polygons and to Ω(n) for convex polygons. To obtain these stronger bounds, we improve known estimates on the number of n-vertex graphs with bounded obstacle number, solving a conjecture by Dujmović and Morin. We also show that if the drawing of some n-vertex graph is given as part of the input, then for some drawings Ω(n²) obstacles are required to turn them into an obstacle representation of the graph. Our bounds are asymptotically tight in several instances. We complement these combinatorial bounds by two complexity results. First, we show that computing the obstacle number of a graph G is fixed-parameter tractable in the vertex cover number of G. Second, we show that, given a graph G and a simple polygon P, it is NP-hard to decide whether G admits an obstacle representation using P as the only obstacle.
Drawings of Complete Multipartite Graphs up to Triangle Flips
Aichholzer, Oswin; Chiu, Man-Kwun; Hoang, Hung P.; et al. (2023)
Leibniz International Proceedings in Informatics (LIPIcs) ~ 39th International Symposium on Computational Geometry (SoCG 2023)
For a drawing of a labeled graph, the rotation of a vertex or crossing is the cyclic order of its incident edges, represented by the labels of their other endpoints. The extended rotation system (ERS) of the drawing is the collection of the rotations of all vertices and crossings. A drawing is simple if each pair of edges has at most one common point. Gioan's Theorem states that for any two simple drawings of the complete graph Kₙ with the same crossing edge pairs, one drawing can be transformed into the other by a sequence of triangle flips (also known as Reidemeister moves of Type 3). This operation refers to the act of moving one edge of a triangular cell formed by three pairwise crossing edges over the opposite crossing of the cell, via a local transformation. We investigate to what extent Gioan-type theorems can be obtained for wider classes of graphs. A necessary (but in general not sufficient) condition for two drawings of a graph to be transformable into each other by a sequence of triangle flips is that they have the same ERS. As our main result, we show that for the large class of complete multipartite graphs, this necessary condition is in fact also sufficient. We present two different proofs of this result, one of which is shorter, while the other one yields a polynomial time algorithm for which the number of needed triangle flips for graphs on n vertices is bounded by O(n¹⁶). The latter proof uses a Carath & eacute;odory-type theorem for simple drawings of complete multipartite graphs, which we believe to be of independent interest. Moreover, we show that our Gioan-type theorem for complete multipartite graphs is essentially tight in the following sense: For the complete bipartite graph Kₘ,ₙ minus two edges and Kₘ,ₙ plus one edge for any m, n ≥ 4, as well as Kₙ minus a 4-cycle for any n ≥ 5, there exist two simple drawings with the same ERS that cannot be transformed into each other using triangle flips. So having the same ERS does not remain sufficient when removing or adding very few edges.
On the Maximum Number of Crossings in Star-Simple Drawings of Kn with No Empty Lens
Felsner, Stefan; Hoffmann, Michael; Knorr, Kristin; et al. (2020)
Lecture Notes in Computer Science ~ Graph Drawing and Network Visualization
A star-simple drawing of a graph is a drawing in which adjacent edges do not cross. In contrast, there is no restriction on the number of crossings between two independent edges. When allowing empty lenses (a face in the arrangement induced by two edges that is bounded by a 2-cycle), two independent edges may cross arbitrarily many times in a star-simple drawing. We consider star-simple drawings of Kn with no empty lens. In this setting we prove an upper bound of 3((n−4)!) on the maximum number of crossings between any pair of edges. It follows that the total number of crossings is finite and upper bounded by n!.
ParkView: Visualizing Monotone Interleavings
Beurskens, Thijs; van den Broek, Steven; Simons, Arjen; et al. (2025)
arXiv
Merge trees are a powerful tool from topological data analysis that is frequently used to analyze scalar fields. The similarity between two merge trees can be captured by an interleaving: a pair of maps between the trees that jointly preserve ancestor relations in the trees. Interleavings can have a complex structure; visualizing them requires a sense of (drawing) order which is not inherent in this purely topological concept. However, in practice it is often desirable to introduce additional geometric constraints, which leads to variants such as labeled or monotone interleavings. Monotone interleavings respect a given order on the leaves of the merge trees and hence have the potential to be visualized in a clear and comprehensive manner. In this paper, we introduce ParkView: a schematic, scalable encoding for monotone interleavings. ParkView captures both maps of the interleaving using an optimal decomposition of both trees into paths and corresponding branches. We prove several structural properties of monotone interleavings, which support a sparse visual encoding using active paths and hedges that can be linked using a maximum of 6 colors for merge trees of arbitrary size. We show how to compute an optimal path-branch decomposition in linear time and illustrate ParkView on a number of real-world datasets.
Drawing Shortest Paths in Geodetic Graphs
Cornelsen, Sabine; Pfister, Maximilian; Förster, Henry; et al. (2022)
Journal of Graph Algorithms and Applications
Motivated by the fact that in a space where shortest paths are unique, no two shortest paths meet twice, we study a question posed by Greg Bodwin: Given a geodetic graph G, i.e., an unweighted graph in which the shortest path between any pair of vertices is unique, is there a philogeodetic drawing of G, i.e., a drawing of G in which the curves of any two shortest paths meet at most once? We answer this question in the negative by showing the existence of geodetic graphs that require some pair of shortest paths to cross at least four times. The bound on the number of crossings is tight for the class of graphs we construct. Furthermore, we exhibit geodetic graphs of diameter two that do not admit a philogeodetic drawing. On the positive side we show that geodetic graphs admit a philogeodetic drawing if both the diameter and the density are very low.
The Number of Edges in Maximal 2-Planar Graphs
Hoffmann, Michael; Reddy, Meghana M. (2023)
39th International Symposium on Computational Geometry
A graph is 2-planar if it has local crossing number two, that is, it can be drawn in the plane such that every edge has at most two crossings. A graph is maximal 2-planar if no edge can be added such that the resulting graph remains 2-planar. A 2-planar graph on n vertices has at most 5n − 10 edges, and some (maximal) 2-planar graphs - referred to as optimal 2-planar - achieve this bound. However, in strong contrast to maximal planar graphs, a maximal 2-planar graph may have fewer than the maximum possible number of edges. In this paper, we determine the minimum edge density of maximal 2-planar graphs by proving that every maximal 2-planar graph on n ≥ 5 vertices has at least 2n edges. We also show that this bound is tight, up to an additive constant. The lower bound is based on an analysis of the degree distribution in specific classes of drawings of the graph. The upper bound construction is verified by carefully exploring the space of admissible drawings using computer support.
Universal geometric graphs
Frati, Fabrizio; Hoffmann, Michael; Tóth, Csaba D. (2023)
Combinatorics, Probability & Computing
We extend the notion of universal graphs to a geometric setting. A geometric graph is universal for a class H of planar graphs if it contains an embedding, that is, a crossing-free drawing, of every graph in H . Our main result is that there exists a geometric graph with n vertices and O(nlogn) edges that is universal for n -vertex forests; this generalises a well-known result by Chung and Graham, which states that there exists an (abstract) graph with n vertices and O(nlogn) edges that contains every n -vertex forest as a subgraph. The upper bound of O(nlogn) edges cannot be improved, even if more than n vertices are allowed. We also prove that every n -vertex convex geometric graph that is universal for n -vertex outerplanar graphs has a near-quadratic number of edges, namely Ωh(n2−1/h) , for every positive integer h ; this almost matches the trivial O(n2) upper bound given by the n -vertex complete convex geometric graph. Finally, we prove that there exists an n -vertex convex geometric graph with n vertices and O(nlogn) edges that is universal for n -vertex caterpillars.
Long Plane Trees
Cabello, Sergio; Hoffmann, Michael; Klost, Katharina; et al. (2022)
Leibniz International Proceedings in Informatics (LIPIcs) ~ 38th International Symposium on Computational Geometry
In the longest plane spanning tree problem, we are given a finite planar point set P, and our task is to find a plane (i.e., noncrossing) spanning tree TOPT for P with maximum total Euclidean edge length |TOPT|. Despite more than two decades of research, it remains open if this problem is NP-hard. Thus, previous efforts have focused on polynomial-time algorithms that produce plane trees whose total edge length approximates |TOPT|. The approximate trees in these algorithms all have small unweighted diameter, typically three or four. It is natural to ask whether this is a common feature of longest plane spanning trees, or an artifact of the specific approximation algorithms. We provide three results to elucidate the interplay between the approximation guarantee and the unweighted diameter of the approximate trees. First, we describe a polynomial-time algorithm to construct a plane tree TALG with diameter at most four and |TALG| = 0.546 · |TOPT|. This constitutes a substantial improvement over the state of the art. Second, we show that a longest plane tree among those with diameter at most three can be found in polynomial time. Third, for any candidate diameter d = 3, we provide upper bounds on the approximation factor that can be achieved by a longest plane tree with diameter at most d (compared to a longest plane tree without constraints).
On the Maximum Number of Crossings in Star-Simple Drawings of Kn with No Empty Lens
Felsner, Stefan; Hoffmann, Michael; Knorr, Kristin; et al. (2022)
Journal of Graph Algorithms and Applications
A star-simple drawing of a graph is a drawing in which adjacent edges do not cross. In contrast, there is no restriction on the number of crossings between two independent edges. We forbid empty lenses, i.e., every lens is required to enclose a vertex, and show that with this restriction 3 ⋅ (n−4)! is an upper bound on the number of crossings between two edges of a star-simple drawing of Kn. It follows that n! bounds the total number of crossings in the drawing. This is the first finite upper bound on the number of crossings in star-simple drawings of the complete graph Kn with no empty lens. For a lower bound we construct a star-simple drawing of Kn with no empty lens in which a pair of edges contributes 5^(n/(2−2)) crossings.
Minimal Representations of Order Types by Geometric Graphs
Aichholzer, Oswin; Balko, Martin; Hoffmann, Michael; et al. (2020)
Journal of Graph Algorithms and Applications
In order to have a compact visualization of the order type of a given point set S, we are interested in geometric graphs on S with few edges that unambiguously display the order type of S. We introduce the concept of exit edges, which prevent the order type from changing under continuous motion of vertices. That is, in the geometric graph on S whose edges are the exit edges, in order to change the order type of S, at least one vertex needs to move across an exit edge. Exit edges have a natural dual characterization, which allows us to efficiently compute them and to bound their number.

Publications 1 - 10 of 23

Michael Hoffmann

Last Name

First Name

ORCID

Organisational unit

Filters

Search Results