On-Line Planarity Testing
From MaRDI portal
Publication:4714554
DOI10.1137/S0097539794280736zbMath0858.68063WikidataQ29391142 ScholiaQ29391142MaRDI QIDQ4714554
Roberto Tamassia, Giuseppe Di Battista
Publication date: 7 November 1996
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Parallel algorithms in computer science (68W10) Data structures (68P05)
Related Items (87)
Outer 1-planar graphs ⋮ SIMULTANEOUS EMBEDDING OF EMBEDDED PLANAR GRAPHS ⋮ Using SPQR-trees to speed up algorithms based on 2-cutset decompositions ⋮ Planar straight-line realizations of 2-trees with prescribed edge lengths ⋮ Atomic Embeddability, Clustered Planarity, and Thickenability ⋮ Linear-time recognition of map graphs with outerplanar witness ⋮ 3-connected reduction for regular graph covers ⋮ On the Hardness and Approximability of Planar Biconnectivity Augmentation ⋮ On RAC drawings of 1-planar graphs ⋮ Topological morphing of planar graphs ⋮ The Optimal Packing of Eight Points in the Real Projective Plane ⋮ Möbius stanchion systems ⋮ Jordan-like characterization of automorphism groups of planar graphs ⋮ Monotone Drawings of Graphs with Fixed Embedding ⋮ On fully diverse sets of geometric objects and graphs ⋮ Bitonic \(st\)-orderings for upward planar graphs: splits and bends in the variable embedding scenario ⋮ Maintaining triconnected components under node expansion ⋮ On the bond polytope ⋮ Upward book embeddability of \(st\)-graphs: complexity and algorithms ⋮ Inserting Multiple Edges into a Planar Graph ⋮ Reconfiguration of connected graph partitions ⋮ Unit-length rectangular drawings of graphs ⋮ Testing upward planarity of partial 2-trees ⋮ Dynamic planar embeddings of dynamic graphs ⋮ Drawing subcubic planar graphs with four slopes and optimal angular resolution ⋮ Small Point-Sets Supporting Graph Stories ⋮ Re-embedding a 1-Plane Graph into a Straight-Line Drawing in Linear Time ⋮ Simultaneous Orthogonal Planarity ⋮ Morphing planar graph drawings through 3D ⋮ Small point-sets supporting graph stories ⋮ A linear-time algorithm for star-shaped drawings of planar graphs with the minimum number of concave corners ⋮ On 2-strong connectivity orientations of mixed graphs and related problems ⋮ On-line convex planarity testing ⋮ Recognizing optimal 1-planar graphs in linear time ⋮ \(\mathsf{T}\)-shape visibility representations of 1-planar graphs ⋮ Graph Stories in Small Area ⋮ Graph stories in small area ⋮ Parameterized complexity of graph planarity with restricted cyclic orders ⋮ Minimum cost star-shaped drawings of plane graphs with a fixed embedding and concave corner constraints ⋮ Fully dynamic representations of interval graphs ⋮ Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph ⋮ Unnamed Item ⋮ Minor-Closed Graph Classes with Bounded Layered Pathwidth ⋮ Extending Steinitz's theorem to upward star-shaped polyhedra and spherical polyhedra ⋮ Planar L-Drawings of Directed Graphs ⋮ Dynamic Distance Hereditary Graphs Using Split Decomposition ⋮ A linear-time algorithm for testing full outer-2-planarity ⋮ Orthogonal graph drawing with flexibility constraints ⋮ Testing the Simultaneous Embeddability of Two Graphs Whose Intersection Is a Biconnected Graph or a Tree ⋮ Re-embedding a 1-plane graph for a straight-line drawing in linear time ⋮ Extending upward planar graph drawings ⋮ Characterizing and recognizing 4-map graphs ⋮ Decremental SPQR-trees for Planar Graphs ⋮ Orthogonal graph drawing with inflexible edges ⋮ A branch-and-cut approach to the crossing number problem ⋮ Using SPQR-trees to speed up recognition algorithms based on 2-cutsets ⋮ Relaxing the constraints of clustered planarity ⋮ Finding a minimum-depth embedding of a planar graph in \(O(n^{4})\) time ⋮ A tighter insertion-based approximation of the crossing number ⋮ Hierarchical partial planarity ⋮ Spherical-Rectangular Drawings ⋮ The partial visibility representation extension problem ⋮ Ortho-polygon visibility representations of embedded graphs ⋮ Parameterized complexity of graph planarity with restricted cyclic orders ⋮ Topological Morphing of Planar Graphs ⋮ An SPQR-Tree Approach to Decide Special Cases of Simultaneous Embedding with Fixed Edges ⋮ Simultaneous FPQ-ordering and hybrid planarity testing ⋮ Fully dynamic algorithm for recognition and modular decomposition of permutation graphs ⋮ Graph isomorphism restricted by lists ⋮ Non-planar core reduction of graphs ⋮ Advances in the Planarization Method: Effective Multiple Edge Insertions ⋮ Testing planarity of geometric automorphisms in linear time ⋮ Lower bounds for electrical reduction on surfaces ⋮ Upward Book Embeddings of st-Graphs ⋮ Testing Full Outer-2-planarity in Linear Time ⋮ Triangulating Planar Graphs While Keeping the Pathwidth Small ⋮ Upward Planarity Testing in Practice ⋮ On finding a biconnected spanning planar subgraph with applications to the facilities layout problem ⋮ NodeTrix planarity testing with small clusters ⋮ An algorithm for constructing star-shaped drawings of plane graphs ⋮ TWO FIXED-PARAMETER TRACTABLE ALGORITHMS FOR TESTING UPWARD PLANARITY ⋮ Planarity of streamed graphs ⋮ Incremental convex planarity testing ⋮ TESTING MUTUAL DUALITY OF PLANAR GRAPHS ⋮ Monotone drawings of graphs with fixed embedding ⋮ Disconnectivity and relative positions in simultaneous embeddings ⋮ Towards area requirements for drawing hierarchically planar graphs
This page was built for publication: On-Line Planarity Testing
