Twins in Subdivision Drawings of Hypergraphs. van Bevern, R., Kanj, I., Komusiewicz, C., Niedermeier, R., & Sorge, M. In Hu, Y. & Nöllenburg, M., editors, GD 2016, volume 9801, of Lecture Notes in Computer Science, pages 67–80. Springer, 2016. ![Twins in Subdivision Drawings of Hypergraphs [link]](https://bibbase.org/img/filetypes/link.svg "link")
Preprint doi abstract bibtex 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.
@incollection{BKK+16,
title = {Twins in Subdivision Drawings of Hypergraphs},
author = {René van Bevern and Iyad Kanj and Christian
Komusiewicz and Rolf Niedermeier and Manuel Sorge},
year = 2016,
date = {2016-12-08},
booktitle = {GD 2016},
editor = {Yifan Hu and Martin Nöllenburg},
volume = {9801},
series = {Lecture Notes in Computer Science},
publisher = {Springer},
url_Preprint = {http://arxiv.org/abs/1511.09389v4},
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 ’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.},
keywords = {algorithmic graph theory, graph modification},
pages = "67--80",
isbn = "978-3-319-50106-2",
doi = "10.1007/978-3-319-50106-2_6",
}
Downloads: 0
{"_id":"2g3Yma3fe9sCmCXgm","bibbaseid":"vanbevern-kanj-komusiewicz-niedermeier-sorge-twinsinsubdivisiondrawingsofhypergraphs-2016","downloads":0,"creationDate":"2016-08-14T04:37:13.693Z","title":"Twins in Subdivision Drawings of Hypergraphs","author_short":["van Bevern, R.","Kanj, I.","Komusiewicz, C.","Niedermeier, R.","Sorge, M."],"year":2016,"bibtype":"incollection","biburl":"http://rvb.su/rvb.bib","bibdata":{"bibtype":"incollection","type":"incollection","title":"Twins in Subdivision Drawings of Hypergraphs","author":[{"firstnames":["René"],"propositions":["van"],"lastnames":["Bevern"],"suffixes":[]},{"firstnames":["Iyad"],"propositions":[],"lastnames":["Kanj"],"suffixes":[]},{"firstnames":["Christian"],"propositions":[],"lastnames":["Komusiewicz"],"suffixes":[]},{"firstnames":["Rolf"],"propositions":[],"lastnames":["Niedermeier"],"suffixes":[]},{"firstnames":["Manuel"],"propositions":[],"lastnames":["Sorge"],"suffixes":[]}],"year":"2016","date":"2016-12-08","booktitle":"GD 2016","editor":[{"firstnames":["Yifan"],"propositions":[],"lastnames":["Hu"],"suffixes":[]},{"firstnames":["Martin"],"propositions":[],"lastnames":["Nöllenburg"],"suffixes":[]}],"volume":"9801","series":"Lecture Notes in Computer Science","publisher":"Springer","url_preprint":"http://arxiv.org/abs/1511.09389v4","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 ’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.","keywords":"algorithmic graph theory, graph modification","pages":"67–80","isbn":"978-3-319-50106-2","doi":"10.1007/978-3-319-50106-2_6","bibtex":"@incollection{BKK+16,\n title =\t {Twins in Subdivision Drawings of Hypergraphs},\n author =\t {René van Bevern and Iyad Kanj and Christian\n Komusiewicz and Rolf Niedermeier and Manuel Sorge},\n year =\t 2016,\n date =\t {2016-12-08},\n booktitle =\t {GD 2016},\n editor =\t {Yifan Hu and Martin Nöllenburg},\n volume =\t {9801},\n series =\t {Lecture Notes in Computer Science},\n publisher =\t {Springer},\n url_Preprint = {http://arxiv.org/abs/1511.09389v4},\n abstract =\t {Visualizing hypergraphs, systems of subsets of some\n universe, has continuously attracted research\n interest in the last decades. We study a natural\n kind of hypergraph visualization called subdivision\n drawings. Dinkla et al. [Comput. Graph. Forum ’12]\n claimed that only few hypergraphs have a subdivision\n drawing. However, this statement seems to be based\n on the assumption (also used in previous work) that\n the input hypergraph does not contain twins, pairs\n of vertices which are in precisely the same\n hyperedges (subsets of the universe). We show that\n such vertices may be necessary for a hypergraph to\n admit a subdivision drawing. As a counterpart, we\n show that the number of such “necessary twins” is\n upper-bounded by a function of the number m of\n hyperedges and a further parameter r of the desired\n drawing related to its number of layers. This leads\n to a linear-time algorithm for determining such\n subdivision draw- ings if m and r are constant; in\n other words, the problem is linear-time\n fixed-parameter tractable with respect to the\n parameters m and r.},\n keywords =\t {algorithmic graph theory, graph modification},\n pages =\t \"67--80\",\n isbn =\t \"978-3-319-50106-2\",\n doi =\t\t \"10.1007/978-3-319-50106-2_6\",\n}\n\n","author_short":["van Bevern, R.","Kanj, I.","Komusiewicz, C.","Niedermeier, R.","Sorge, M."],"editor_short":["Hu, Y.","Nöllenburg, M."],"key":"BKK+16","id":"BKK+16","bibbaseid":"vanbevern-kanj-komusiewicz-niedermeier-sorge-twinsinsubdivisiondrawingsofhypergraphs-2016","role":"author","urls":{" preprint":"http://arxiv.org/abs/1511.09389v4"},"keyword":["algorithmic graph theory","graph modification"],"metadata":{"authorlinks":{"van bevern, r":"https://rvb.su/"}},"downloads":0,"html":""},"search_terms":["twins","subdivision","drawings","hypergraphs","van bevern","kanj","komusiewicz","niedermeier","sorge"],"keywords":["algorithmic graph theory","graph modification"],"authorIDs":["2fwXJtKDCNhaSNr5s"],"dataSources":["SMwzc9Bzq5Np5ikev","G5GefJqqu2DtnCZXz"]}