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