Twins in subdivision drawings of hypergraphs

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

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

3 Цитирования (Scopus)


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.

Язык оригиналаанглийский
Название основной публикацииGraph Drawing and Network Visualization - 24th International Symposium, GD 2016, Revised Selected Papers
РедакторыMartin Nollenburg, Yifan Hu
ИздательSpringer-Verlag GmbH and Co. KG
Число страниц14
ISBN (печатное издание)9783319501055
СостояниеЭлектронная публикация перед печатью - 8 дек. 2016
Событие24th International Symposium on Graph Drawing and Network Visualization, GD 2016 - Athens, Греция
Продолжительность: 19 сент. 201621 сент. 2016

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том9801 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349


Конференция24th International Symposium on Graph Drawing and Network Visualization, GD 2016


Подробные сведения о темах исследования «Twins in subdivision drawings of hypergraphs». Вместе они формируют уникальный семантический отпечаток (fingerprint).