Abstract: We present a simplified version of the DFS-based Left-Right planarity testing and embedding algorithm implemented in Pigale which has been considered as the fastest implemented one [J.M. Boyer, P.F. Cortese, M. Patrignani, and G. Di Battista. Stop minding your P's and Q's: implementing fast and simple DFS-based planarity and embedding algorithm. In Graph Drawing, volume 2912 of Lecture Notes in Computer Science, pages 25-36. Springer, 2004.]. We give here a simple full justification of the algorithm, based on a preliminary extended study of topological properties of DFS trees.
Recommendations
Cited in
(22)- A characterization of planar graphs by Trémaux orders
- Plane trees and classical mathematics
- On the geometry of a class of plane trees
- Planar trees, slalom curves and hyperbolic knots
- Odd or even on plane trees
- Planar rooted trees and non-associative exponential series
- Testing gap \(k\)-planarity is NP-complete
- Treetopes and their graphs
- scientific article; zbMATH DE number 3929029 (Why is no real title available?)
- scientific article; zbMATH DE number 1504603 (Why is no real title available?)
- On Cotree-Critical and DFS Cotree-Critical Graphs
- \(k\)-planar graphs
- Planarity algorithms via PQ-trees (extended abstract)
- Trémaux trees and planarity
- A computational approach to Conway's thrackle conjecture
- On the parameterized complexity of the structure of lineal topologies (depth-first spanning trees) of finite graphs: the number of leaves
- An annotated review on graph drawing and its applications
- Trémaux trees and planarity
- On the parameterized complexity of lineal topologies (depth-first spanning trees) with many or few leaves
- Constrained planarity in practice -- engineering the synchronized planarity algorithm
- Covering simple orthogonal polygons with rectangles
- Clustered planarity testing revisited
This page was built for publication: TRÉMAUX TREES AND PLANARITY
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5493892)
