2015/11/15 by René van Bevern, Iyad Kanj, van Bevern, René +7
Computer Science · Engineering · Environmental Science · #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Manufacturing Process and Optimization #Remote Sensing and LiDAR Applications
paper · pdf · doi:10.48550/arxiv.1511.09389
openalex publication_date 2015/11/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A support or realization of a hypergraph H is a graph G on the same vertex as H such that for each hyperedge of 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.