Drawing Bipartite Graphs in Two Layers with Specified Crossings

Logo poskytovatele

Varování

Publikace nespadá pod Pedagogickou 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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.