Twins in Subdivision Drawings of Hypergraphs

DOI10.1007/978-3-319-50106-2_6MaRDI QIDQ2961505zbMATH OpenOpenAlexFDO

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

Publication date 21 February 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.09389

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Hypergraphs (05C65) Parameterized complexity, tractability and kernelization (68Q27)

Abstract: 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$.

Recommendations

• Twin Vertices in Hypergraphs
• Subdivision Drawings of Hypergraphs
• Twins in graphs
• Twin subgraphs and core-semiperiphery-periphery structures
• Twins of rayless graphs
• Subdivision of hypergraphs and their colorings
• scientific article; zbMATH DE number 2080095
• On twin edge colorings of graphs
• Doubly connected domination subdivision numbers of graphs
• Paired-domination subdivision numbers of graphs

Cites work

• An Almost Linear-Time Algorithm for Graph Realization
• Blocks of hypergraphs. Applied to hypergraphs and outerplanarity
• Diagrammatic Representation and Inference
• Graph theory
• How to Draw a Graph
• How to draw a hypergraph
• Hypergraph planarity and the complexity of drawing venn diagrams
• Minimum tree supports for hypergraphs and low-concurrency Euler diagrams
• On planar supports for hypergraphs
• On the Desirability of Acyclic Database Schemes
• Orthogonal Hypergraph Drawing for Improved Visibility
• Parameterized algorithms
• Partition refinement techniques: an interesting algorithmic tool kit
• Path-based supports for hypergraphs
• Polynomial-time data reduction for the subset interconnection design problem
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Subdivision Drawings of Hypergraphs
• The clustering matroid and the optimal clustering tree

Cited in

(5)

• Subdivision Drawings of Hypergraphs
• Twin Vertices in Hypergraphs
• The role of twins in computing planar supports of hypergraphs
• C-planarity testing of embedded clustered graphs with bounded dual carving-width
• Twins in graphs

This page was built for publication: Twins in Subdivision Drawings of Hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2961505)