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

Proceedings paper

Field of Study

Informatics

Confidentiality degree

is not subject to a state or trade secret

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.