article · Electronics and Communications in Japan (Part I Communications) · 1984

Embedding planar graphs using PQ‐tree algorithms

Norishige Chiba, Takao Nishizeki, Shigenobu Abe, Takao Ozawa

Cited by 5Abstract and details only

Abstract

Abstract The problems of testing the planarity of a graph and of embedding a planar graph in a plane arise in many applications. This paper presents a simple linear algorithm for the latter problem. the algorithm is based on the “vertex‐addition algorithm” of Lempel, Even and Cederbaum for planarity testing and is a slight modification of Booth and Lueker's implementation of the testing algorithm using a PQ‐tree. Compared with the embedding algorithm known as the “path‐addition” algorithm of Hopcroft and Tarjan, our algorithm is conceptually simple and easy to understand or implement.

Cite this paper

APA 7

Chiba, N., Nishizeki, T., Abe, S., & Ozawa, T. (1984). Embedding planar graphs using PQ‐tree algorithms. Electronics and Communications in Japan (Part I Communications), 67(7), 12–20. https://doi.org/10.1002/ecja.4400670703

MLA 9

Chiba, Norishige, et al. “Embedding planar graphs using PQ‐tree algorithms.” Electronics and Communications in Japan (Part I Communications), vol. 67, no. 7, 1984, pp. 12–20, https://doi.org/10.1002/ecja.4400670703.

Chicago

Chiba, Norishige, Takao Nishizeki, Shigenobu Abe, and Takao Ozawa. 1984. “Embedding planar graphs using PQ‐tree algorithms.” Electronics and Communications in Japan (Part I Communications) 67 (7): 12–20. https://doi.org/10.1002/ecja.4400670703.

Harvard

Chiba, N. et al. (1984) ‘Embedding planar graphs using PQ‐tree algorithms’, Electronics and Communications in Japan (Part I Communications), 67(7), pp. 12–20. Available at: https://doi.org/10.1002/ecja.4400670703.

BibTeX

@article{chiba1984embedding,
  title = {{Embedding planar graphs using PQ‐tree algorithms}},
  author = {Chiba, Norishige and Nishizeki, Takao and Abe, Shigenobu and Ozawa, Takao},
  journal = {Electronics and Communications in Japan (Part I Communications)},
  volume = {67},
  number = {7},
  pages = {12--20},
  year = {1984},
  doi = {10.1002/ecja.4400670703}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.