7 citations · 31 across the 24 of their papers we have counts for
5 papers · 1 filter
Properties of Large 2-Crossing-Critical Graphs
Drago Bokal, Markus Chimani, Alexander Nover +4
A -crossing-critical graph is one that has crossing number at least but each of its proper subgraphs has crossing number less than . Recently, a set of explicit construct…
Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics
Markus Chimani, Max Ilsen, Tilo Wiedera
We present a thorough experimental evaluation of several crossing minimization heuristics that are based on the construction and iterative improvement of a planarization, i.e., a p…
Crossing Numbers and Stress of Random Graphs
Markus Chimani, Hanna Döring, Matthias Reitzner
Consider a random geometric graph over a random point process in . Two points are connected by an edge if and only if their distance is bounded by a prescribed distan…
How Not to Characterize Planar-emulable Graphs
Markus Chimani, Martin Derka, Petr Hliněný +1
We investigate the question of which graphs have planar emulators (a locally-surjective homomorphism from some finite planar graph) -- a problem raised already in Fellows' thesis (…
A Tighter Insertion-based Approximation of the Crossing Number
Markus Chimani, Petr Hlineny
Let G be a planar graph and F a set of additional edges not yet in G. The multiple edge insertion problem (MEI) asks for a drawing of G+F with the minimum number of pairwise edge c…