Drawing Bipartite Graphs in Two Layers with Specified Crossings

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Autoři	DIWAN Ajit Arvind ROY Bodhayan GHOSH Subir Kumar
Rok publikování	2019
Druh	Článek ve sborníku
Konference	5th International Conference of Algorithms and Discrete Applied Mathematics (CALDAM 2019)
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
Doi	http://dx.doi.org/10.1007/978-3-030-11509-8_9
Klíčová slova	Abstract topological graph; Bipartite graph; Permutation graph; Two-layer drawing
Popis	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.
Související projekty:	Structural properties, parameterized tractability and hardness in combinatorial problems