1. Simultaneous FPQ-ordering and hybrid planarity testing.
- Author
-
Liotta, Giuseppe, Rutter, Ignaz, and Tappini, Alessandra
- Subjects
- *
DEFINITIONS - Abstract
We introduce and study a constrained planarity testing problem, called 1 -Fixed Constrained Planarity , and prove that this problem can be solved in quadratic time for biconnected graphs. Our solution is based on a novel definition of fixedness that makes it possible to simplify and extend known techniques about Simultaneous PQ-Ordering. We exploit this result to study different versions of the hybrid planarity testing problem. Namely, we show polynomial-time solutions for a variant of NodeTrix Planarity with fixed sides, for PolyLink Planarity , and for Clique Planarity with fixed sides. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF