Ein Planaritätstest für planar-konvexe Grapheneinbettungen mit linearer Komplexität (Q760440)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Ein Planaritätstest für planar-konvexe Grapheneinbettungen mit linearer Komplexität |
scientific article |
Statements
Ein Planaritätstest für planar-konvexe Grapheneinbettungen mit linearer Komplexität (English)
0 references
1984
0 references
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.
0 references
criterion of planarity
0 references
optimal planar layout
0 references
cost function
0 references