Efficient planarity testing

Hopcroft, J., & Tarjan, R. (1974). Efficient planarity testing. ACM.

Type

Journal article

Intellectual base

Primary research

Year

1974

DOI

10.1145/321850.321852

DOI registrant

Association for Computing Machinery

Link

https://doi.org/10.1145/321850.321852

Cited by

2 citations across 2 artifacts.

Each citation links to the sentence it supports in the citing article.

Domain-specific

• Planarity
  • Planarity testing can be decided in linear time (Hopcroft and Tarjan, 1974)

    This sourceGives a depth-first-search algorithm that decides in O(V) time whether a graph can be embedded in the plane.

    SupportedVerified against the source

    Read by an automated reader; not a human review. How support was checked

• Planarity testing
  • Planarity algorithms incrementally construct an embedding, use depth-first-search structure, or reduce to connectivity constraints, with linear-time methods returning a rotation system or Kuratowski subdivision certificate.

Verification

Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.

Does it back the claim? Read against the text for 1 of 2 citations: 1 supported. Each verdict is shown under its citation below, with what in the work backs the sentence.

Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.

See how references were verified.

Registry ID ref:78e8fb655d9a · see in the full table