Two-layer Drawings of Bipartite Graphs

DIWAN, Ajit Arvind, Bodhayan ROY and Subir Kumar GHOSH. Two-layer Drawings of Bipartite Graphs. Eurocomb 2017. 2017, p. 351-357.

Basic information

Original name

Two-layer Drawings of Bipartite Graphs

Authors

DIWAN, Ajit Arvind, Bodhayan ROY and Subir Kumar GHOSH

Edition

Eurocomb 2017. p. 351-357, 7 pp. 2017

---

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

Informatics

Confidentiality degree

není předmětem státního či obchodního tajemství

Organization unit

Faculty of Informatics

Keywords in English

abstract topological graph; two-layer drawing; bipartite graph

Tags

International impact, Reviewed

---

Abstract

V originále

We give a polynomial-time algorithm to decide whether a connected bipartite graph admits a two-layer drawing in the plane such that a specified subset of pairs of disjoint edges cross. We consider the problem of deciding whether there exists such a drawing in which a specified subset of triples of pairwise crossing edges are concurrent. We give a necessary condition for the same and conjecture that it is sufficient.