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. (C) 2021 Elsevier B.V. All rights reserved.

Simultaneous FPQ-ordering and hybrid planarity testing

Liotta G.;Tappini A.
2021

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. (C) 2021 Elsevier B.V. All rights reserved.
2021
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11391/1542057
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 4
social impact