2017
Two-layer Drawings of Bipartite Graphs
DIWAN, Ajit Arvind, Bodhayan ROY and Subir Kumar GHOSHBasic 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
Changed: 10/4/2018 10:45, Bodhayan Roy, Ph.D.
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.