Drawing Bipartite Graphs in Two Layers with Specified Crossings

Warning

This publication doesn't include Faculty of Sports Studies. 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:	Structural properties, parameterized tractability and hardness in combinatorial problems