Strip planarity testing for embedded planar graphs

DOI10.1007/S00453-016-0128-9zbMATH Open1360.68486DBLPjournals/algorithmica/AngeliniLBF17arXiv1309.0683OpenAlexW1816979946WikidataQ62046544 ScholiaQ62046544MaRDI QIDQ524364FDOQ524364

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

Publication date: 2 May 2017

Published in: Algorithmica (Search for Journal in Brave)

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.

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

Recommendations

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

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)

Cites Work

• Depth-First Search and Linear Graph Algorithms
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Efficient Planarity Testing
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• On the computational complexity of upward and rectilinear planarity testing
• 2-Isomorphic Graphs
• A Kuratowski-type theorem for planarity of partially embedded graphs
• Title not available (Why is that?)
• Drawing Graphs in the Plane with a Prescribed Outer Face and Polynomial Area
• Algorithms for plane representations of acyclic digraphs
• Radial Level Planarity Testing and Embedding in Linear Time
• Upward drawings of triconnected digraphs.
• Title not available (Why is that?)
• Short path queries in planar graphs in constant time
• On embedding a cycle in a plane graph
• A characterization of level planar graphs
• Straight-line drawing algorithms for hierarchical graphs and clustered graphs
• Toward a theory of planarity: Hanani-Tutte and planarity variants
• The Importance of Being Proper
• Advances on Testing C-Planarity of Embedded Flat Clustered Graphs
• Towards the Hanani-Tutte Theorem for Clustered Graphs
• Upward Spirality and Upward Planarity Testing
• Efficient C-Planarity Testing for Embedded Flat Clustered Graphs with Small Faces
• Clustered Planarity: Small Clusters in Cycles and Eulerian Graphs
• On the Characterization of Level Planar Trees by Minimal Patterns
• Clustered Planarity: Embedded Clustered Graphs with Two-Component Clusters
• Title not available (Why is that?)
• Upward Planar Drawing of Single-Source Acyclic Digraphs
• Clustering Cycles into Cycles of Clusters
• Planarity Testing and Optimal Edge Insertion with Embedding Constraints
• Compatible Connectivity-Augmentation of Planar Disconnected Graphs
• Minimum Level Nonplanar Patterns for Trees
• SOFSEM 2004: Theory and Practice of Computer Science
• Planarity for clustered graphs
• Straight-line rectangular drawings of clustered graphs
• Improving the running time of embedded upward planarity testing

Cited In (17)

• Upward Book Embeddings of st-Graphs
• Clustered planarity = flat clustered planarity
• Crossing minimization in perturbed drawings
• Crossing minimization in perturbed drawings
• Maintaining triconnected components under node expansion
• Embedding Graphs into Embedded Graphs
• Beyond Clustered Planar Graphs
• Upward book embeddability of \(st\)-graphs: complexity and algorithms
• C-planarity testing of embedded clustered graphs with bounded dual carving-width
• \(c\)-planarity of embedded cyclic \(c\)-graphs
• Extending upward planar graph drawings
• Clustered planarity with pipes
• Testing Planarity of Partially Embedded Graphs
• Embedding graphs into embedded graphs
• Hanani-Tutte for radial planarity. II
• Hanani-Tutte for approximating maps of graphs
• Radial Level Planarity with Fixed Embedding

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)