TY - JOUR
AU - van Bevern, René
AU - Kanj, Iyad
AU - Komusiewicz, Christian
AU - Niedermeier, Rolf
AU - Sorge, Manuel
PY - 2024/05/16
Y2 - 2024/11/08
TI - The role of twins in computing planar supports of hypergraphs
JF - Journal of Graph Algorithms and Applications
JA - JGAA
VL - 28
IS - 1
SE -
DO - 10.7155/jgaa.v28i1.2927
UR - https://jgaa.info/index.php/jgaa/article/view/2927
SP - 51-79
AB - <pre>A <em>support</em> or <em>realization </em>of a hypergraph $\mathcal{H}$ is a graph \(G\) on the same vertex set as \(\mathcal{H}\) such that </pre><pre>for each hyperedge of $\mathcal{H}$ it holds that its vertices induce a </pre><pre> connected subgraph of $G$.</pre><pre> The NP-hard problem of finding a <em>planar</em> support</pre><pre> has applications in hypergraph drawing</pre><pre> and network design.</pre><pre> Previous algorithms for the problem assume that</pre><pre><em> twins</em>---pairs of vertices that are in precisely</pre><pre> the same hyperedges---can safely be removed from the input hypergraph.</pre><pre> We prove that this assumption is generally wrong,</pre><pre> yet that the number of twins</pre><pre> necessary for a hypergraph </pre><pre> to have a planar support only depends on its number of hyperedges.</pre><pre> We give an explicit upper bound on the number of twins</pre><pre> necessary</pre><pre> for a hypergraph with \(m\) hyperedges</pre><pre> to have an \(r\)-outerplanar support,</pre><pre> which depends only on \(r\) and \(m\).</pre><pre> Since all additional twins can be safely removed,</pre><pre> we obtain a linear-time</pre><pre> algorithm for computing \(r\)-outerplanar supports</pre><pre> for hypergraphs with \(m\) hyperedges</pre><pre> </pre><pre> if $m$ and $r$</pre><pre> are constant; in other words, the problem is fixed-parameter linear-time</pre><pre> solvable with respect to the parameters $m$ and $r$.</pre>
ER -