14 citations · 54 across the 20 of their papers we have counts for
28 papers
The Number of Edges in Maximal 2-planar Graphs
Michael Hoffmann, Meghana M. Reddy
A graph is -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 -planar if no…
Drawings of Complete Multipartite Graphs Up to Triangle Flips
Oswin Aichholzer, Man-Kwun Chiu, Hung P. Hoang +5
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 r…
Bounding and computing obstacle numbers of graphs
Martin Balko, Steven Chaplick, Robert Ganian +4
An obstacle representation of a graph consists of a set of pairwise disjoint simply-connected closed regions and a one-to-one mapping of the vertices of to points such that…
Long Plane Trees
Sergio Cabello, Michael Hoffmann, Katharina Klost +2
In the longest plane spanning tree problem, we are given a finite planar point set , and our task is to find a plane (i.e., noncrossing) spanning tree for $\mathcal{P}…
Mad Science is Provably Hard: Puzzles in Hearthstone's Boomsday Lab are NP-hard
Michael Hoffmann, Jayson Lynch, Andrew Winslow
We consider the computational complexity of winning this turn (mate-in-1 or "finding lethal") in Hearthstone as well as several other single turn puzzle types introduced in the Boo…
On the Maximum Number of Crossings in Star-Simple Drawings of with No Empty Lens
Stefan Felsner, Michael Hoffmann, Kristin Knorr +1
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. W…