Drawing Bipartite Graphs in Two Layers with Specified Crossings

Investor logo

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

DIWAN Ajit Arvind ROY Bodhayan GHOSH Subir Kumar

Year of publication 2019
Type Article in Proceedings
Conference 5th International Conference of Algorithms and Discrete Applied Mathematics (CALDAM 2019)
MU Faculty or unit

Faculty of Informatics

Citation
Doi http://dx.doi.org/10.1007/978-3-030-11509-8_9
Keywords Abstract topological graph; Bipartite graph; Permutation graph; Two-layer drawing
Description We give a polynomial-time algorithm to decide whether a bipartite graph admits a two-layer drawing in the plane such that a specified subset of pairs of edges cross. This is a generalization of the problem of recognizing permutation graphs, and we generalize the characterization of permutation graphs.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.