Geodesic
Simple Recognition of Halin Graphs and Their Generalizations
Journal of Graph Algorithms and Applications, Tome 20 (2016) no. 2, pp. 323-346.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

We describe and implement two local reduction rules that can be used to recognize Halin graphs in linear time, avoiding the complicated planarity testing step of previous linear time Halin graph recognition algorithms. The same two rules can be used as the basis for linear-time algorithms for other algorithmic problems on Halin graphs, including decomposing these graphs into a tree and a cycle, finding a Hamiltonian cycle, or constructing a planar embedding. These reduction rules can also be used to recognize a broader class of polyhedral graphs. These graphs, which we call the D3-reducible graphs, are the dual graphs of the polyhedra formed by gluing pyramids together on their triangular faces; their treewidth is bounded, and they necessarily have Lombardi drawings. 
@article{JGAA_2016_20_2_a6,
     author = {David Eppstein},
     title = {Simple {Recognition} of {Halin} {Graphs} and {Their
Generalizations}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {323--346},
     publisher = {mathdoc},
     volume = {20},
     number = {2},
     year = {2016},
     doi = {10.7155/jgaa.00395},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00395/}
}
TY  - JOUR
AU  - David Eppstein
TI  - Simple Recognition of Halin Graphs and Their
Generalizations
JO  - Journal of Graph Algorithms and Applications
PY  - 2016
SP  - 323
EP  - 346
VL  - 20
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00395/
DO  - 10.7155/jgaa.00395
LA  - en
ID  - JGAA_2016_20_2_a6
ER  - 
%0 Journal Article
%A David Eppstein
%T Simple Recognition of Halin Graphs and Their
Generalizations
%J Journal of Graph Algorithms and Applications
%D 2016
%P 323-346
%V 20
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00395/
%R 10.7155/jgaa.00395
%G en
%F JGAA_2016_20_2_a6
David Eppstein. Simple Recognition of Halin Graphs and Their
Generalizations. Journal of Graph Algorithms and Applications, Tome 20 (2016) no. 2, pp. 323-346. doi : 10.7155/jgaa.00395. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00395/

Cité par Sources :