Simultaneous planar drawing problem solved with vertex integrity parameter
Ramsey Meets Simultaneous Planarity: Vertex Integrity and Pathwidth
Data Structures and Algorithms
Summary
This paper studies how to draw multiple graphs that share some connections on the same set of points without their lines crossing. The authors developed a method that can efficiently determine if such drawings are possible by focusing on a property called vertex integrity, which relates to how the graphs are connected overall. They also show that using a different graph complexity measure, called pathwidth, does not help, as the problem remains hard even when pathwidth is small. A new technique called Ramsey pruning was extended to help with this problem.
What this means in practice
- •For network designers: Determine if multiple overlapping network layouts can be visualized simultaneously without crossing lines for better clarity in network management.
- •For software engineers: Improve tools that visualize related datasets by efficiently checking if combined graphs can be drawn together without overlaps.
A theory result. No direct application yet.
Authors
Thomas Depian, Simon D. Fink, Alexander Firbas, Robert Ganian, Matthias Pfretzschner, Ignaz Rutter
Abstract
We study the following simultaneous embedding problem: Given k graphs on the same vertex set with the same pairwise intersection, do they admit planar drawings that coincide on their shared graph? We establish fixed-parameter tractability with respect to the vertex integrity of the union graph (that is, the union of the input graphs) plus k, resolving an open question and generalizing the known algorithm parameterized by vertex cover number plus k. Our main technical contribution on the way towards this result is the extension of the recently introduced Ramsey pruning technique beyond ordering problems. Finally, we complement our tractability result with a lower bound that establishes NP-hardness when both k and the pathwidth of the union graph are bounded by constants, ruling out a generalization of our main result to path- or treewidth.