zbMATH — the first resource for mathematics

Two-layer planarization: Improving on parameterized algorithmics. (English) Zbl 1117.68456
Vojtáš, Peter (ed.) et al., SOFSEM 2005: Theory and practice of computer science. 31st conference on current trends in theory and practice of computer science, Liptovský Ján, Slovakia, January 22–28, 2005. Proceedings. Berlin: Springer (ISBN 3-540-24302-X/pbk). Lecture Notes in Computer Science 3381, 137-146 (2005).
Summary: A bipartite graph is biplanar if the vertices can be placed on two parallel lines in the plane such that there are no edge crossings when edges are drawn as straight-line segments. We study two problems:
– 2-Layer Planarization: can \(k\) edges be deleted from a given graph \(G\) so that the remaining graph is biplanar?
– 1-Layer Planarization: same question, but the order of the vertices on one layer is fixed.
For the entire collection see [Zbl 1069.68013].

68R10 Graph theory (including graph drawing) in computer science
05C62 Graph representations (geometric and intersection representations, etc.)
05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: DOI