Strip planarity testing for embedded planar graphs

DOI10.1007/S00453-016-0128-9MaRDI QIDQ524364zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati

Publication date 2 May 2017

Published in Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

planarityclustered planarityembedded graphslevel planarityupward planarity

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) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: In this paper we introduce and study the strip planarity testing problem, which takes as an input a planar graph $G(V,E)$ and a function $gamma:Vightarrow1,2,dots,k$ and asks whether a planar drawing of $G$ exists such that each edge is monotone in the $y$-direction and, for any $u,vinV$ with $gamma(u)<gamma(v)$, it holds $y(u)<y(v)$. The problem has strong relationships with some of the most deeply studied variants of the planarity testing problem, such as clustered planarity, upward planarity, and level planarity. We show that the problem is polynomial-time solvable if $G$ has a fixed planar embedding.

Recommendations

• Strip planarity testing
• Multilevel planarity
• Multilevel planarity
• Level Planar Embedding in Linear Time
• Drawing planar graphs on a curve.

Cites work

• scientific article; zbMATH DE number 3885930 (Why is no real title available?)
• scientific article; zbMATH DE number 1979538 (Why is no real title available?)
• 2-Isomorphic Graphs
• A Kuratowski-type theorem for planarity of partially embedded graphs
• A characterization of level planar graphs
• Advances on Testing C-Planarity of Embedded Flat Clustered Graphs
• Algorithms for plane representations of acyclic digraphs
• Clustered Planarity: Embedded Clustered Graphs with Two-Component Clusters
• Clustered planarity: small clusters in cycles and Eulerian graphs
• Clustering Cycles into Cycles of Clusters
• Compatible connectivity-augmentation of planar disconnected graphs
• Depth-First Search and Linear Graph Algorithms
• Drawing graphs in the plane with a prescribed outer face and polynomial area
• Efficient Planarity Testing
• Efficient \(C\)-planarity testing for embedded flat clustered graphs with small faces
• Improving the running time of embedded upward planarity testing
• Minimum Level Nonplanar Patterns for Trees
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• On embedding a cycle in a plane graph
• On the characterization of level planar trees by minimal patterns
• On the computational complexity of upward and rectilinear planarity testing
• Planarity Testing and Optimal Edge Insertion with Embedding Constraints
• Planarity for clustered graphs
• Radial Level Planarity Testing and Embedding in Linear Time
• SOFSEM 2004: Theory and Practice of Computer Science
• Short path queries in planar graphs in constant time
• Straight-line drawing algorithms for hierarchical graphs and clustered graphs
• Straight-line rectangular drawings of clustered graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Testing planarity of partially embedded graphs
• The importance of being proper (in clustered-level planarity and \(T\)-level planarity)
• Toward a theory of planarity: Hanani-Tutte and planarity variants
• Towards the Hanani-Tutte theorem for clustered graphs
• Upward Planar Drawing of Single-Source Acyclic Digraphs
• Upward drawings of triconnected digraphs.
• Upward spirality and upward planarity testing

Cited in

(18)

• Clustered planarity = flat clustered planarity
• Crossing minimization in perturbed drawings
• Crossing minimization in perturbed drawings
• HV-planarity: algorithms and complexity
• Embedding Graphs into Embedded Graphs
• Maintaining triconnected components under node expansion
• Multilevel planarity
• Radial level planarity with fixed embedding
• Beyond Clustered Planar Graphs
• Upward book embeddings of st-graphs
• Upward book embeddability of \(st\)-graphs: complexity and algorithms
• C-planarity testing of embedded clustered graphs with bounded dual carving-width
• Clustered planarity with pipes
• Testing Planarity of Partially Embedded Graphs
• Embedding graphs into embedded graphs
• Strip planarity testing
• Hanani-Tutte for radial planarity. II
• Hanani-Tutte for approximating maps of graphs

This page was built for publication: Strip planarity testing for embedded planar graphs

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