## René van Bevern, Iyad Kanj, Christian Komusiewicz, Rolf Niedermeier, and
Manuel Sorge.
Twins in subdivision drawings of hypergraphs.
In *Proceedings of the 24th International Symposium on Graph
Drawing and Network Visualization (GD'16), Athens, Greece*, volume 9801 of
*Lecture Notes in Computer Science*, pages 67–80. Springer, 2016.

Visualizing hypergraphs, systems of subsets of some
universe, has continuously attracted research interest
in the last decades. We study a natural kind of
hypergraph visualization called subdivision drawings.
Dinkla et al. [Comput. Graph. Forum ’12] claimed that
only few hypergraphs have a subdivision
drawing. However, this statement seems to be based on
the assumption (also used in previous work) that the
input hypergraph does not contain twins, pairs of
vertices which are in precisely the same hyperedges
(subsets of the universe). We show that such vertices
may be necessary for a hypergraph to admit a
subdivision drawing. As a counterpart, we show that
the number of such “necessary twins” is upper-bounded
by a function of the number m of hyperedges and a
further parameter r of the desired drawing related to
its number of layers. This leads to a linear-time
algorithm for determining such subdivision draw- ings
if m and r are constant; in other words, the problem
is linear-time fixed-parameter tractable with respect
to the parameters m and r.

[ bib |
DOI |
http ]
Back

*This file was generated by
bibtex2html 1.98.*