1 citations · 1 across the 5 of their papers we have counts for
6 papers · 1 filter
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…
Simple Topological Drawings of -Planar Graphs
Michael Hoffmann, Chih-Hung Liu, Meghana M. Reddy +1
Every finite graph admits a \emph{simple (topological) drawing}, that is, a drawing where every pair of edges intersects in at most one point. However, in combination with other re…
Plane Spanning Trees in Edge-Colored Simple Drawings of
Oswin Aichholzer, Michael Hoffmann, Johannes Obenaus +5
Károlyi, Pach, and Tóth proved that every 2-edge-colored straight-line drawing of the complete graph contains a monochromatic plane spanning tree. It is open if this statement gene…
Drawing Shortest Paths in Geodetic Graphs
Sabine Cornelsen, Maximilian Pfister, Henry Förster +4
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 , i.e.,…
Universal Geometric Graphs
Fabrizio Frati, Michael Hoffmann, Csaba D. Tóth
We introduce and study the problem of constructing geometric graphs that have few vertices and edges and that are universal for planar graphs or for some sub-class of planar graphs…