Left-right planarity test

In graph theory, a branch of mathematics, the left-right planarity test or de Fraysseix–Rosenstiehl planarity criterion[1] is a characterization of planar graphs based on the properties of the depth-first search trees, published by de Fraysseix and Rosenstiehl (1982, 1985)[2][3] and used by them with Patrice Ossona de Mendez to develop a linear time planarity testing algorithm.[4][5] In a 2003 experimental comparison of six planarity testing algorithms, this was one of the fastest algorithms tested.[6]

  1. ^ Auer, Christopher; Gleißner, Andreas; Hanauer, Kathrin; Vetter, Sebastian (2013), "Testing planarity by switching trains", Graph Drawing: 20th International Symposium, GD 2012, Redmond, WA, USA, September 19-21, 2012, Revised Selected Papers, Lecture Notes in Computer Science, vol. 7704, Berlin: Springer, pp. 557–558, doi:10.1007/978-3-642-36763-2_51.
  2. ^ de Fraysseix, H.; Rosenstiehl, P. (1982), "A depth-first-search characterization of planarity", Graph Theory (Cambridge, 1981), Annals of Discrete Mathematics, vol. 13, North-Holland, Amsterdam-New York, pp. 75–80, MR 0671906.
  3. ^ de Fraysseix, H.; Rosenstiehl, P. (1985), "A characterization of planar graphs by Trémaux orders", Combinatorica, 5 (2): 127–135, doi:10.1007/BF02579375, MR 0815578, S2CID 35423242.
  4. ^ de Fraysseix, Hubert; Ossona de Mendez, Patrice; Rosenstiehl, Pierre (2006), "Trémaux trees and planarity", International Journal of Foundations of Computer Science, 17 (5): 1017–1029, arXiv:math.CO/0610935, doi:10.1142/S0129054106004248, MR 2270949.
  5. ^ de Fraysseix, Hubert; Ossona de Mendez, Patrice (2012), "Trémaux trees and planarity", European Journal of Combinatorics, 33 (3): 279–293, arXiv:math/0610935, doi:10.1016/j.ejc.2011.09.012, MR 2864415.
  6. ^ Boyer, John M.; Cortese, Pier Francesco; Patrignani, Maurizio; Di Battista, Giuseppe (2004), "Stop minding your P's and Q's: implementing a fast and simple DFS-based planarity testing and embedding algorithm", Graph Drawing: 11th International Symposium, GD 2003 Perugia, Italy, September 21-24, 2003, Revised Papers, Lecture Notes in Computer Science, vol. 2912, Berlin: Springer, pp. 25–36, doi:10.1007/978-3-540-24595-7_3, MR 2177580.