Ein Planaritätstest für planar-konvexe Grapheneinbettungen mit linearer Komplexität (Q760440)

Replying to results of the diploma-examination [Optimale Einbettungen von Graphen mit festem Rand, Diplomarbeit, Saarbrücken (1966)] by the first author and of a paper by the second author [Math. Ann. 167, 214-223 (1966; Zbl 0144.231)] the authors essentially prove a criterion of planarity. This criterion can be used in order to calculate an optimal planar layout to a given cost function. The fundamental idea is that either a non-planar layout is not convex or the sequence of edges being incident to one vertex has been changed in opposite to a planar layout of this group.