Geodesic
The role of twins in computing planar supports of hypergraphs
René van Bevern1 ; Iyad Kanj2 ; Christian Komusiewicz3 ; Rolf Niedermeier4 ; Manuel Sorge5
1 Huawei Technologies Co., Ltd.
2 DePaul University
3 Friedrich Schiller University Jena
4 Algorithmics and Computational Complexity, Faculty IV, TU Berlin
5 Institute of Logic and Computation, TU Wien
Journal of Graph Algorithms and Applications, Tome 28 (2024) no. 1, pp. 51-79.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

A support or realization of a hypergraph $\mathcal{H}$ is a graph \(G\) on the same vertex set as \(\mathcal{H}\) such that for each hyperedge of $\mathcal{H}$ it holds that its vertices induce a connected subgraph of $G$. The NP-hard problem of finding a planar support has applications in hypergraph drawing and network design. Previous algorithms for the problem assume that twins---pairs of vertices that are in precisely the same hyperedges---can safely be removed from the input hypergraph. We prove that this assumption is generally wrong, yet that the number of twins necessary for a hypergraph to have a planar support only depends on its number of hyperedges. We give an explicit upper bound on the number of twins necessary for a hypergraph with \(m\) hyperedges to have an \(r\)-outerplanar support, which depends only on \(r\) and \(m\). Since all additional twins can be safely removed, we obtain a linear-time algorithm for computing \(r\)-outerplanar supports for hypergraphs with \(m\) hyperedges if $m$ and $r$ are constant; in other words, the problem is fixed-parameter linear-time solvable with respect to the parameters $m$ and $r$.
DOI : 10.7155/jgaa.v28i1.2927
Keywords: Subdivision drawings, NP-hard problem, r-outerplanar graphs, sphere-cut branch decomposition

René van Bevern 1 ; Iyad Kanj 2 ; Christian Komusiewicz 3 ; Rolf Niedermeier 4 ; Manuel Sorge 5

1 Huawei Technologies Co., Ltd.
2 DePaul University
3 Friedrich Schiller University Jena
4 Algorithmics and Computational Complexity, Faculty IV, TU Berlin
5 Institute of Logic and Computation, TU Wien 
@article{JGAA_2024_28_1_a2,
     author = {Ren\'e van Bevern and Iyad Kanj and Christian Komusiewicz and Rolf Niedermeier and Manuel Sorge},
     title = {The role of twins in computing planar supports of hypergraphs},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {51--79},
     publisher = {mathdoc},
     volume = {28},
     number = {1},
     year = {2024},
     doi = {10.7155/jgaa.v28i1.2927},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2927/}
}
TY  - JOUR
AU  - René van Bevern
AU  - Iyad Kanj
AU  - Christian Komusiewicz
AU  - Rolf Niedermeier
AU  - Manuel Sorge
TI  - The role of twins in computing planar supports of hypergraphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2024
SP  - 51
EP  - 79
VL  - 28
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2927/
DO  - 10.7155/jgaa.v28i1.2927
LA  - en
ID  - JGAA_2024_28_1_a2
ER  - 
%0 Journal Article
%A René van Bevern
%A Iyad Kanj
%A Christian Komusiewicz
%A Rolf Niedermeier
%A Manuel Sorge
%T The role of twins in computing planar supports of hypergraphs
%J Journal of Graph Algorithms and Applications
%D 2024
%P 51-79
%V 28
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2927/
%R 10.7155/jgaa.v28i1.2927
%G en
%F JGAA_2024_28_1_a2
René van Bevern; Iyad Kanj; Christian Komusiewicz; Rolf Niedermeier; Manuel Sorge. The role of twins in computing planar supports of hypergraphs. Journal of Graph Algorithms and Applications, Tome 28 (2024) no. 1, pp. 51-79. doi : 10.7155/jgaa.v28i1.2927. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2927/

Cité par Sources :