MPI-INF Logo
MPI-INF/SWS Research Reports 1991-2021

2. Number - only D1

MPI-I-94-117

On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm

Mehlhorn, Kurt and Mutzel, Petra

March 1994, 8 pages.

.
Status: available - back from printing

We give a detailed description of the embedding phase of the Hopcroft and Tarjan planarity testing algorithm. The embedding phase runs in linear time. An implementation based on this paper can be found in [Mehlhorn-Mutzel-Naeher-94].

  • MPI-I-94-117.pdfMPI-I-94-117.pdfMPI-I-94-117.ps.gz
  • Attachement: MPI-I-94-117.ps.gz (52 KBytes); MPI-I-94-117.pdf (131 KBytes)

URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1994-117

Hide details for BibTeXBibTeX
@TECHREPORT{MehlhornMutzel94,
  AUTHOR = {Mehlhorn, Kurt and Mutzel, Petra},
  TITLE = {On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-94-117},
  MONTH = {March},
  YEAR = {1994},
  ISSN = {0946-011X},
}