bibkey: haas2003henneberg
authors: Ruth Haas, David Orden, Günter Rote, Francisco Santos, Brigitte Servatius, Herman Servatius, Diane Souvaine, Ileana Streinu, Walter Whiteley
year: 2003
title: Planar Minimally Rigid Graphs and Pseudo-Triangulations
doi: 10.1016/j.comgeo.2004.07.003
url: https://arxiv.org/abs/math/0307347v1
claim: Section 2 Lemma 2.1 characterizes Laman graphs by Henneberg constructions starting from an edge; planarity is not required for that lemma.
strata_touched:
  - D5/S3/Combinatorics/Graph/Laman/History
license: citation-only
triage: anchor

Henneberg characterization of Laman graphs

Section 2, pages 4–5, starts the construction with an edge on two vertices. Type I joins a fresh vertex to two old vertices. Type II removes an edge and joins a fresh vertex to its two endpoints and a third vertex. The text explicitly says these constructions work for general, not necessarily planar, Laman graphs. Lemma 2.1 states that a graph is Laman if and only if it has a Henneberg construction. Its reverse proof removes a suitable degree-two or degree-three vertex while preserving the Laman property.

This is a known general combinatorial theorem. No planar embedding or generic geometric placement is a hypothesis of the receiving finite-history theorem. Laman’s original DOI is 10.1007/BF01534980; its full original text is not used as a verified locator here.

Verified locator

• Versioned manuscript: https://arxiv.org/abs/math/0307347v1
• Published DOI: https://doi.org/10.1016/j.comgeo.2004.07.003