Simultaneous FPQ-ordering and hybrid planarity testing

DOI10.1007/978-3-030-38919-2_51zbMATH Open1504.68177arXiv1910.10113OpenAlexW4212823911MaRDI QIDQ2034412FDOQ2034412

Giuseppe Liotta, Alessandra Tappini, Ignaz Rutter

Publication date: 22 June 2021

Published in: Theoretical Computer Science, SOFSEM 2020: Theory and Practice of Computer Science (Search for Journal in Brave)

Abstract: We study the interplay between embedding constrained planarity and hybrid planarity testing. We consider 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 new definition of fixedness that makes it possible to simplify and extend known techniques about Simultaneous PQ-Ordering. We apply these results to different variants of hybrid planarity testing, including a relaxation of NodeTrix Planarity with fixed sides, that allows rows and columns to be independently permuted.

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

Recommendations

• Simultaneous FPQ-ordering and hybrid planarity testing
• Simultaneous PQ-ordering with applications to constrained embedding problems
• Simultaneous PQ-ordering with applications to constrained embedding problems
• Simultaneous embedding: edge orderings, relative positions, cutvertices
• Planarity Testing and Optimal Edge Insertion with Embedding Constraints

zbMATH Keywords

graph drawinghybrid planarity testingsimultaneous FPQ-ordering

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Cites Work

• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Title not available (Why is that?)
• On-Line Planarity Testing
• Testing Planarity of Partially Embedded Graphs
• Planarity Testing and Optimal Edge Insertion with Embedding Constraints
• Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems
• NodeTrix planarity testing with small clusters
• Computing NodeTrix Representations of Clustered Graphs
• Intersection-Link Representations of Graphs
• Beyond level planarity: cyclic, torus, and simultaneous level planarity
• Planar Graphs with Topological Constraints
• Computing k-modal embeddings of planar digraphs
• (k, p)-Planarity: A Relaxation of Hybrid Planarity

Cited In (7)

• Maintaining triconnected components under node expansion
• Beyond Clustered Planar Graphs
• A user study on hybrid graph visualizations
• Synchronized Planarity with Applications to Constrained Planarity Problems
• \((k,p)\)-planarity: a relaxation of hybrid planarity
• Parameterized complexity of graph planarity with restricted cyclic orders
• Parameterized complexity of graph planarity with restricted cyclic orders

Uses Software

• NodeTrix

This page was built for publication: Simultaneous FPQ-ordering and hybrid planarity testing

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