TY - GEN

T1 - Twins in subdivision drawings of hypergraphs

AU - van Bevern, René

AU - Kanj, Iyad

AU - Komusiewicz, Christian

AU - Niedermeier, Rolf

AU - Sorge, Manuel

PY - 2016/12/8

Y1 - 2016/12/8

N2 - 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 drawings 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.

AB - 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 drawings 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.

UR - http://www.scopus.com/inward/record.url?scp=85007398584&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-50106-2_6

DO - 10.1007/978-3-319-50106-2_6

M3 - Conference contribution

AN - SCOPUS:85007398584

SN - 9783319501055

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 67

EP - 80

BT - Graph Drawing and Network Visualization - 24th International Symposium, GD 2016, Revised Selected Papers

A2 - Nollenburg, Martin

A2 - Hu, Yifan

PB - Springer-Verlag GmbH and Co. KG

T2 - 24th International Symposium on Graph Drawing and Network Visualization, GD 2016

Y2 - 19 September 2016 through 21 September 2016

ER -