Twins in subdivision drawings of hypergraphs

René van Bevern, Iyad Kanj, Christian Komusiewicz, Rolf Niedermeier, Manuel Sorge

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

3 Citations (Scopus)

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

Original languageEnglish
Title of host publicationGraph Drawing and Network Visualization - 24th International Symposium, GD 2016, Revised Selected Papers
EditorsMartin Nollenburg, Yifan Hu
PublisherSpringer-Verlag GmbH and Co. KG
Pages67-80
Number of pages14
ISBN (Print)9783319501055
DOIs
Publication statusE-pub ahead of print - 8 Dec 2016
Event24th International Symposium on Graph Drawing and Network Visualization, GD 2016 - Athens, Greece
Duration: 19 Sep 201621 Sep 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9801 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference24th International Symposium on Graph Drawing and Network Visualization, GD 2016
CountryGreece
CityAthens
Period19.09.201621.09.2016

Fingerprint

Dive into the research topics of 'Twins in subdivision drawings of hypergraphs'. Together they form a unique fingerprint.

Cite this