Standard
Twins in subdivision drawings of hypergraphs. / van Bevern, René; Kanj, Iyad; Komusiewicz, Christian et al.
Graph Drawing and Network Visualization - 24th International Symposium, GD 2016, Revised Selected Papers. ed. / Martin Nollenburg; Yifan Hu. Springer-Verlag GmbH and Co. KG, 2016. p. 67-80 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9801 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
van Bevern, R, Kanj, I, Komusiewicz, C, Niedermeier, R & Sorge, M 2016,
Twins in subdivision drawings of hypergraphs. in M Nollenburg & Y Hu (eds),
Graph Drawing and Network Visualization - 24th International Symposium, GD 2016, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9801 LNCS, Springer-Verlag GmbH and Co. KG, pp. 67-80, 24th International Symposium on Graph Drawing and Network Visualization, GD 2016, Athens, Greece,
19.09.2016.
https://doi.org/10.1007/978-3-319-50106-2_6
APA
van Bevern, R., Kanj, I., Komusiewicz, C., Niedermeier, R., & Sorge, M. (2016).
Twins in subdivision drawings of hypergraphs. In M. Nollenburg, & Y. Hu (Eds.),
Graph Drawing and Network Visualization - 24th International Symposium, GD 2016, Revised Selected Papers (pp. 67-80). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9801 LNCS). Springer-Verlag GmbH and Co. KG.
https://doi.org/10.1007/978-3-319-50106-2_6
Vancouver
van Bevern R, Kanj I, Komusiewicz C, Niedermeier R, Sorge M.
Twins in subdivision drawings of hypergraphs. In Nollenburg M, Hu Y, editors, Graph Drawing and Network Visualization - 24th International Symposium, GD 2016, Revised Selected Papers. Springer-Verlag GmbH and Co. KG. 2016. p. 67-80. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Epub 2016 Dec 8. doi: 10.1007/978-3-319-50106-2_6
Author
van Bevern, René ; Kanj, Iyad ; Komusiewicz, Christian et al. /
Twins in subdivision drawings of hypergraphs. Graph Drawing and Network Visualization - 24th International Symposium, GD 2016, Revised Selected Papers. editor / Martin Nollenburg ; Yifan Hu. Springer-Verlag GmbH and Co. KG, 2016. pp. 67-80 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
BibTeX
@inproceedings{c78782605f444ed6a42585ab01745c4c,
title = "Twins in subdivision drawings of hypergraphs",
abstract = "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 {\textquoteright}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.",
author = "{van Bevern}, Ren{\'e} and Iyad Kanj and Christian Komusiewicz and Rolf Niedermeier and Manuel Sorge",
year = "2016",
month = dec,
day = "8",
doi = "10.1007/978-3-319-50106-2_6",
language = "English",
isbn = "9783319501055",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag GmbH and Co. KG",
pages = "67--80",
editor = "Martin Nollenburg and Yifan Hu",
booktitle = "Graph Drawing and Network Visualization - 24th International Symposium, GD 2016, Revised Selected Papers",
address = "Germany",
note = "24th International Symposium on Graph Drawing and Network Visualization, GD 2016 ; Conference date: 19-09-2016 Through 21-09-2016",
}
RIS
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 -
